二义性文法的特点

  • 每个二义性文法都不是LR的

  • 某些类型的二义性文法在语言的描述和实现中很有用,因为其更简短、更自然

    二义性文法

    ① E→ E+E
    ② E→ E*E
    ③ E→ ( E )
    ④ E→ id

    非二义性文法

    ① E → E + T
    ② E → T
    ③ T → T * F
    ④ T → F
    ⑤ F → ( E )
    ⑥ F → id

二义性算术表达式文法的LR(0)分析器

文法

E→E+E
E→E*E
E→(E)
E→id

FOLLOW(E) = { +,*,), $ }

用优先级和结合性解决冲突

二义性算术表达式文法的SLR分析表

文法

E→E+E
E→E*E
E→(E)
E→id

FOLLOW(E)={ +, *, ), $ }

例:二义性if 语句文法的LR分析

S → i S|i S e S|a

二义性if语句文法的SLR分析表

二义性文法的使用

应该保守地使用二义性文法,并且必须在严格控制之下使用,因为稍有不慎就会导致语法分析器所识别的语言出现偏差

LR分析中的错误处理

  • 语法错误的检测

    • 当LR分析器在查询分析表并发现一个报错条目时,就检测到了一个语法错误
  • 错误恢复策略

    • 恐慌模式错误恢复
    • 短语层次错误恢复

恐慌模式错误恢复

  • 从栈顶向下扫描,直到发现某个状态si,它有一个对应于某个非终结符A的GOTO目标,可以认为从这个A推导出的串中包含错误
  • 然后丢弃0个或多个输入符号,直到发现一个可能合法地跟在A之后的符号a为止。
  • 之后将si+1 = GOTO(si , A)压入栈中,继续进行正常的语法分析

短语层次错误恢复

  • 检查LR分析表中的每一个报错条目,并根据语言的使用方法来决定程序员所犯的何种错误最有可能引起这个语法错误
  • 然后构造出适当的恢复过程

例:算数表达式文法的LR分析器

文法

E→E+E
E→E*E
E→(E)
E→id

VT ={+,*,(,),id, $}

带有错误处理子程序的算术表达式文法LR分析表

错误处理例程

  • e1:将状态3压入栈中,发出诊断信息“缺少运算分量”
  • e2:从输入中删除“)”,发出诊断信息“不匹配的右括号”
  • e3:将状态4压入栈中,发出诊断信息“缺少运算符”
  • e4:将状态9压入栈中,发出诊断信息“缺少右括号“
最后修改日期:2020年6月1日

留言

撰写回覆或留言