语法复习题(1)

《编译原理》语法分析复习题1

P→+aP| +a

提取公共左因子，文法变为G’(S)： S→aPS’| *aPS’

S’→ *aPS’ |ε

P→+aP’ P’→P| ε

7．设有文法G[S]:

S→a|（T）|? T→T,S|S

试给出句子(a,a,a)的最左推导。 【解】(1) (a,a,a)的最左推导

S=>(T) =>(T,S) =>( T,S,S) =>( S,S,S) =>(a,S,S) =>(a,a,S) =>(a,a,a)

8．设有文法G[S]:

S→S*S|S+S|(S)|i

该文法是否为二义文法,并说明理由？

【解】该文法是二义文法，因为该文法存在句子i*i+i,该句子有两棵不同的语法树如图所示。

S S i (1) S S S i + S i S i S * + S i (2) * S i

9．设有如下文法： G[E]：E→EWT|T T→T/F|F

F→（E）|a|b|c W→+|-

证明符号串a/(b-c)是句子。

解答：有推导E?T?T/F?F/F?a/F?a/(E)?a/(EWT)? a/(TWT)? a/(FWT)? a/(bWT)? a/(b-T)? a/(b-c)，即从文法开始符号E能够推导出a/(b-c)，所以a/(b-c)是文法G[E]的句子。 10．设有文法G[S]: S→aAcB|Bd A→AaB|c B→bScA|b

该文法句型aAcbBdcc的句柄是_______Bd_____________。

5