国防科技大学 编译原理 第3讲 高级程序设计语言的语法描述

距离上次更新已经 1534 天了，文章内容可能已经过时。

课程主页：

https://www.icourse163.org/course/NUDT-1003101005?tid=1460976445

这次回顾第3讲：高级程序设计语言的语法描述。

第3讲 高级程序设计语言的语法描述

文法

• 文法：描述语言的语法结构的形式规则

• 假设我们有如下文法：

• ```
  <句子> -> <主语><谓语><间接宾语><直接宾语>
  <主语> -> <代词>
  <谓语> -> <动词>
  <间接宾语> -> <代词>
  <直接宾语> -> <冠词> <名词>
  <代词> -> He
  <代词> -> me
  <名词> -> book
  <冠词> -> a
  <动词> -> gave

  - 考虑句子：He gave me a book.
  
  - ```
      <句子>
    =><主语><谓语><间接宾语><直接宾语>
    =><代词><谓语><间接宾语><直接宾语>
    =>He <谓语><间接宾语><直接宾语>
    =>He <动词> <间接宾语><直接宾语>
    =>He gave <间接宾语><直接宾语>
    =>He gave <代词> <直接宾语>
    =>He gave me <直接宾语>
    =>He gave me <冠词><名词>
    =>He gave me a <名词>
    =>He gave me a book

语法描述的几个基本概念

• 字母表：一个有穷字符集，记为$\mathrm{\Sigma }$

• 字母表中每个元素称为字符

• $\mathrm{\Sigma }$上的字(也叫字符串) 是指由$\mathrm{\Sigma }$中的字符所构成的一个有穷序列

• 不包含任何字符的序列称为空字，记为$\epsilon$

• 用${\mathrm{\Sigma }}^{\star }$表示$\mathrm{\Sigma }$上的所有字的全体，包含空字$\epsilon$

  • 例如: 设 $\mathrm{\Sigma }=\{a,b\}$，则

$${\mathrm{\Sigma }}^{\star }=\{\epsilon ,a,b,aa,ab,ba,bb,aaa,\dots \}$$

• ${\mathrm{\Sigma }}^{\star }$的子集$U$和$V$的连接（积）定义为

  $$UV＝\{\alpha \beta |\alpha \in U\mathrm{\&}\beta \in V\}$$

• 示例：$U=\{a,aa\},V=\{b,bb\},UV=\{ab,abb,aab,aabb\}$

• $V$自身的$n$次积记为

  $$V^n=\underset{n\mathrm{个}}{\underbrace{V\dots V}}$$

• $V^0=\{\epsilon \}$

• $V^{\star }$是$V$的闭包：$V^{\star }=V^0\cup V^1\cup V^2\dots$

• $V^{+}$是$V$的正规闭包：$V^{+}=V{V}^{\star }$

  • 例子：

    $$U=\{a,aa\}$$

  • 那么：

    $$\begin{array}{rl}{U}^{\star }& =\{\epsilon ,a,aa,aaa,aaaa,\dots \}\\ U^{+}& =\{a,aa,aaa,aaaa,\dots \}\end{array}$$

上下文无关文法

• 上下文无关文法$G$是一个四元组

  $$G=(V_T,V_N,S,P)$$

• 其中

  • $V_T$：终结符(Terminal)集合(非空)
  • $V_N$：非终结符(Noterminal)集合(非空)，且$V_T\cap V_N=\varnothing$
  • $S$：文法的开始符号，$S\in V_N$
  • $P$：产生式集合(有限)，每个产生式形式为
    • $P\to \alpha ，P\in V_N，\alpha \in (V_T\cup V_N{)}^{\star }$
  • 开始符$S$至少必须在某个产生式的左部出现一次

• 上下文无关文法还有一种描述形式，称为巴科斯范式(BNF)

  • “ →”用“::=”表示

例子

定义只含$+，\star$的算术表达式的文法

$$G=<\{i,+,\star ,(,)\}，\{E\},E,P>$$

其中，$P$的定义如下：

• $E\to i$
• $E\to E+E$
• $E\to E\star E$
• $E\to (E)$

一些约定

• 约定

  $$\begin{array}{l}P\to {\alpha }_1\\ P\to {\alpha }_2\stackrel{\text{ 可缩写为 }}{\Rightarrow }\\ \dots \\ P\to {\alpha }_{\mathrm{n}}\end{array}P\to {\alpha }_1\left|{\alpha }_2\right|\dots \mid {\alpha }_{\mathrm{n}}$$

• 其中，“$|$”读成“或”，称${\alpha }_i$为$P$的一个候选式

  • 表示一个文法时，通常只给出开始符号和产生式

• 之前的文法可以简写为

  $$G(E)：E\to i|E+E|E\star E|(E)$$

文法生成语言

推导

• 定义：称$\alpha A\beta$直接推出$\alpha \gamma \beta$，即

  $$\alpha A\beta \Rightarrow \alpha \gamma \beta$$

  仅当$A\to \gamma$是一个产生式，且$\alpha ,\beta \in (V_T\cup V_N{)}^{\star }$。

• 如果${\alpha }_1\Rightarrow {\alpha }_2\Rightarrow \dots \Rightarrow {\alpha }_n$，则我们称这个序列是从${\alpha }_1$到${\alpha }_n$的一个推导。若存在一个从${\alpha }_1$到${\alpha }_n$的推导，则称${\alpha }_1$可以推导出${\alpha }_n$。

• 对文法$G(E)：E\to i|E+E|E\star E|(E)$

  $$E\Rightarrow (E)\Rightarrow (E+E)\Rightarrow (i+E)\Rightarrow (i+i)$$

• ${\alpha }_1\stackrel{\star }{\Rightarrow }{\alpha }_n$：从${\alpha }_1$出发，经过$0$步或若干步推出${\alpha }_n$

• ${\alpha }_1\stackrel{+}{\Rightarrow }{\alpha }_n$：从${\alpha }_1$出发，经过$1$步或若干步推出${\alpha }_n$

• $\alpha \Rightarrow 𝛽$ ：即$𝛼=𝛽$或$\alpha \stackrel{+}{\Rightarrow }\beta$

  • <句子> $\stackrel{\star }{\Rightarrow }$ He gave me a book
  • <句子> $\stackrel{+}{\Rightarrow }$ He gave me a book
  • He gave <间接宾语><直接宾语>$\stackrel{+}{\Rightarrow }$He gave me <冠词> <名词>

之前例子的推导过程：

句型、句子和语言

• 假定$G$是一个文法，$S$是它的开始符号。

• 如果$S\stackrel{\star }{\Rightarrow }\alpha$，则称$\alpha$是一个句型。

• 仅含终结符号的句型是一个句子。

• 文法$G$所产生的句子的全体是一个语言，记为$L(G)$:

  $$L(G)=\{\alpha |S\stackrel{+}{\Rightarrow }\alpha ,\alpha \in V_T^{\star }\}$$

例子

证明$(i\star i+i)$是文法

$$G(E)：E\to i|E+E|E\star E|(E)$$

的一个句子。

证明：

$$\begin{array}{rl}E& \Rightarrow (E)\\ & \Rightarrow (E+E)\\ & \Rightarrow (E\star E+E)\\ & \Rightarrow (i\star E+E)\\ & \Rightarrow (i\star i+E)\\ & \Rightarrow (i\star i+i)\end{array}$$

所以$(i+i)$是文法$G$的句子，$E,(E),(E\star E+E),\dots ,(i\star i+i)$是句型。

从文法到语言

例1

• 设文法$$G_1(A)：A\to c|Ab$$

• $G_1(A)$产生的语言是什么?

  • 以$c$开头，后继若干个$b$

    $$L(G_1)=\{c,cb,cbb,\dots \}$$
  • $$\begin{array}{rl}A& \Rightarrow c\\ A& \Rightarrow Ab\\ & \Rightarrow cb\\ A& \Rightarrow Ab\\ & \Rightarrow Abb\\ & \Rightarrow Abbb\\ & \Rightarrow \dots \\ & \Rightarrow Ab\dots b\\ & \Rightarrow cb\dots b\end{array}$$

例2

• 设文法

  $$\begin{array}{rl}{G}_2(S):& S\to AB\\ & A\to aA|a\\ & B\to bB|b\end{array}$$

• $G_2(S)$产生的语言是什么?

  $$L(G_2)=\{a^m{b}^n|m,n>0\}$$
• $$\begin{array}{rl}S& \Rightarrow AB\\ A& \Rightarrow a\\ A& \Rightarrow aA\\ & \Rightarrow aaA\\ & \Rightarrow aaaA\\ & \Rightarrow \dots \\ & \Rightarrow a\dots aA\\ & \Rightarrow a\dots aa\\ B& \Rightarrow b\\ B& \Rightarrow bB\\ & \Rightarrow bbB\\ & \Rightarrow bbbB\\ & \Rightarrow \dots \\ & \Rightarrow b\dots bB\\ & \Rightarrow b\dots bb\end{array}$$

例3

请给出产生语言为$\{a^n{b}^n|n\ge 1\}$的文法

$$\begin{array}{rl}{G}_3(S):& S\to aSb\\ & S\to ab\end{array}$$

例4

请给出产生语言为$\{a^m{b}^n|1\le n\le m\le 2n\}$的文法

$$\begin{array}{rl}{G}_4(S):& S\to ab|aab\\ & S\to aSb|aaSb\end{array}$$

推导与语法树

最左推导和最右推导

• 从一个句型到另一个句型的推导往往不唯一

  $$\begin{array}{rl}E+E& \Rightarrow i+E\Rightarrow i+i\\ E+E& \Rightarrow E+i\Rightarrow i+i\end{array}$$

• 最左推导：任何一步$\alpha \Rightarrow \beta$都是对$\alpha$中的最左非终结符进行替换

• 最右推导：任何一步$\alpha \Rightarrow \beta$都是对$\alpha$中的最右非终结符进行替换

语法树

• 用一张图表示一个句型的推导，称为语法树
• 一棵语法树是不同推导过程的共性抽象

语法树与二义性(ambiguity)

• 一个句型是否只对应唯一一棵语法树？考虑如下例子：

• $G(E)：E\to i|E+E|E\star E|(E)$是二义的(ambiguous)

• $(i\star i+i)$对应了两棵语法树

  

具体定义：

• 文法的二义性：如果一个文法存在某个句子对应两棵不同的语法树，则说这个文法是二义的

  • 例如$G(E)：E\to i|E+E|E\star E|(E)$

  • 可以将其改写为无二义文法$G^{\prime }(E)$：

    

• 语言的二义性：一个语言是二义的，如果对它不存在无二义的文法

  • 对于语言$L$，可能存在$G$和$G^{\prime }$，使得$L(G)=L(G^{\prime })=L$，有可能其中一个文法为二义的， 另一个为无二义的
  • 例如John saw Mary in a boat.是二义的，因为in a boat可以修饰Mary或者John。

• 二义性问题是不可判定问题，即不存在一个算法，它能在有限步骤内，确切地判定一个文法是否是二义的

• 但可以找到一组无二义文法的充分条件

形式语言鸟瞰

• 乔姆斯基(Chomsky)是美国当代有重大影响的语言学家

• 乔姆斯基于1956年建立形式语言体系，他把文法分成四种类型：$0,1,2,3$型

• 与上下文无关文法一样，它们都由四部分组成，但对产生式的限制有所不同

  • $G=(V_T，V_N，S，P)$

    • $V_T$：终结符(Terminal)集合(非空)

    • $V_N$：非终结符(Noterminal)集合(非空)，且$V_T\cap V_N=\varnothing$

    • $S$：文法的开始符号，$S\in V_N$

    • $P$：产生式集合(有限)

四种文法分别如下：

• 0型(短语文法，图灵机)
  • 产生式形如：$\alpha \to \beta$
  • 其中：$\alpha \in (V_T\cup V_N{)}^{\star }$且至少含有一个非终结符；$\beta \in (V_T\cup V_N{)}^{\star }$
• 1型(上下文有关文法，线性界限自动机)
  • 产生式形如：$\alpha \to \beta$
  • 其中：$|\alpha |\le |\beta |$，仅$S\to \epsilon$例外
• 2型(上下文无关文法，非确定下推自动机)
  • 产生式形如： $A\to \beta$
  • 其中：$A\in V_N；\beta \in (V_T\cup V_N{)}^{\star }$
• 3型(正规文法，有限自动机)
  • 产生式形如：$A\to \alpha B$或$A\to \alpha$
    • 其中：$\alpha \in V_T^{\star };A,B\in V_N$（右线性文法）
  • 产生式形如：$A\to B\alpha$或$A\to \alpha$
    • 其中：$\alpha \in V_T^{\star };A,B\in V_N$（左线性文法）

四种类型文法描述能力比较

上下文无关文法与上下文有关文法

例1

$L_5=\{a^n{b}^n|n\ge 1\}$不能由正规文法(3型)产生，但可由上下文无关文法产生

$$G_5(S)：S\to aSb|ab$$

例2

$L_6=\{a^n{b}^n{c}^n|n\ge 1\}$不能由上下文无关文法产生，但可由上下文有关文法产生

$$\begin{array}{rl}{G}_6(S):& S\to aSBC|aBC\\ & CB\to BC\\ & aB\to ab\\ & bB\to bb\\ & bC\to bc\\ & cC\to cc\end{array}$$

推导例子：

$$\begin{array}{rl}& S\\ \Rightarrow & aSBC\\ \Rightarrow & aaSBCBC\\ \Rightarrow & aaaBCBCBC\\ \Rightarrow & aaaBBCCBC\\ \Rightarrow & aaaBBCBCC\\ \Rightarrow & aaaBBBCCC\\ \Rightarrow & aaabBBCCC\\ \Rightarrow & aaabbBCCC\\ \Rightarrow & aaabbbCCC\\ \Rightarrow & aaabbbcCC\\ \Rightarrow & aaabbbccC\\ \Rightarrow & aaabbbccc\end{array}$$

小结

• 程序设计语言不是上下文无关语言，甚至不是上下文有关语言
• $L_7=\{\alpha c\alpha |\alpha \in \{a,b{\}}^{\star }\}$不能由上下文无关文法产生，甚至连上下文有关文法也不能产生，只能由$0$型文法产生
  • $L_7$对应了
    • 标识符引用
    • 过程调用过程中，“形-实参数的对应性”(如个数，顺序和类型一致性)
• 对于现今程序设计语言，在编译程序中，仍然采用上下文无关文法来描述其语言结构
  • 这是一种权衡