2.2 语法定义

练习2.2.1

考虑下面的上下文无关文法
$$S\rightarrow SS+ | S S * |a$$

1. 试说明如何使用该文法生成串aa+a*.
2. 试为这个串构造语法分析树
3. 该文法生成的语言是什么。请证明你的答案

答案

1. $[ S\rightarrow SS* \rightarrow SS+S* \rightarrow aS+S* \rightarrow aa+S* \rightarrow aa+a* $[
2. 语法树如下

1. L是一个包含乘法和加法的运算表达式的后序表达

练习2.2.2

下面的各个文法生成什么语言？证明你的答案

1. $[ S \rightarrow 0S1|01 $[
2. $[ S \rightarrow +SS|-SS|a $[
3. $[ S \rightarrow S(S)S| \epsilon $[
4. $[ S \rightarrow aSbS|bSaS| \epsilon $[
5. $[ S \rightarrow a | S+S | SS | S* | (S) $[

练习2.2.4

为下面的各个语言构建无二义性的上下文无关文法。证明你的文法都是正确的。

1. 用后缀方式表示的算术表达式
2. 由逗号分隔开的左结合的标识符列表
3. 由逗号分隔开的右结合的标识符列表
4. 由整数、标识符、四个二目运算符+-*/构成的算术表达式
5. 在4的运算符中增加单目+和单目-构成的袁术表达式

答案

1. 
   $$ exp \rightarrow exp exp - $$
   $$\space\space | exp \space exp + $$
   $$\space\space | exp \space exp * $$
   $$\space\space | exp \space exp / $$
   $$ | num $$