首页
后端开发
C
LR分析法中的文法二义性与推导过程

LR分析法中的文法二义性与推导过程

24 次浏览 0 条评论
doc
doc

文法二义性证明

文法 1

E -> -EE | -E | a | b | c

证明: 该文法对于输入串"-a"存在两棵不同的语法分析树，故存在二义性。

  • 语法分析树1: E -> -EE -> -aE -> -aa
  • 语法分析树2: E -> -E -> -a

文法 2

P -> PaP | cP | Pe | f

证明: 该文法对于输入串"cPe"存在两棵不同的语法分析树，故存在二义性。

  • 语法分析树1: P -> PaP -> cPaP -> cPeP -> cPee
  • 语法分析树2: P -> Pe -> cPe

最左推导与最右推导

文法:

S -> aB | bA

A -> aS | bAA | a

B -> bS | aBB | b

输入串:

aaabbba

最左推导:

S -> aB 
  -> aaBB 
  -> aaaBBB 
  -> aaabBB 
  -> aaabbSB 
  -> aaabbbaB
  -> aaabbbab

最右推导:

S -> aB 
  -> aBBb
  -> aBab
  -> aaBBbab
  -> aaabBbab
  -> aaabbSBbab
  -> aaabbbaBbab
  -> aaabbbab
doc 文件大小：36KB