3.3 假设有文法
exp → exp addop term | t e r m
addop → + | -
term → term mulop factor | f a c t o r
mulop → *
factor → ( e x p ) | n u m b e r
则为下面的表达式写出最左推导、分析树以及抽象语法树:
a. 3+4*5-6 b. 3*(4-5+6) c. 3-(4+5*6)
3.4 下面的文法生成字母表之上的所有正则表达式(以前曾在算符前后加上了引号,这是
因为竖线既是一个算符又是一个元字符):
rexp → rexp "|" re x p
| rexp re x p
| rexp "*"
| "(" rexp ")"
| l e t t e r
a. 利用这个文法为正则表达式( a b | b ) *给出一个推导。
b. 说明该文法有二义性。
c. 重写该文法以使算符建立正确的优先关系(参见第 2章)。
d. (c)的答案给二进制算符带来怎样的结合性?为什么?
3.5 为包括了常量t r u e和f a l s e、算符a n d、o r和n o t,以及括号的布尔表达式编写一
个文法。确保给予o r比a n d低的优先权,而a n d的优先权比n o t低,并允许n o t重复使
用,如在布尔表达式中的not not true。另外还需保证该文法没有二义性。
3.6 考虑以下表示简化的类L I S P表达式的文法:
lexp → atom | l i s t
atom → n u m b e r | i d e n t i f i e r
list → ( lexp-seq )
lexp-seq → lexp-seq lexp | l e x p
a. 为串(a 23 (m x y))分别写出一个最左推导和一个最右推导。
第 3章 上下文无关文法及分析 1 0 1
下载
1