最左推导、最右推导及其语法树构建
2019-05-05 本文已影响399人
Yinvoker
相关文章
最左推导
定义
在最左推导中，总是选择每个句型的最左非终结符号。
[句型] 如果S=》a，其中S是文法G的开始符号，我们可以称a是G的一个句型，当a是一个终结符时，此时这个句型可以称为句子。
[非终结符号] 可以继续向下推导的符号
例子
有文法：
E -> E +E | E * E | - E | ( E ) | id
需要推出串 - ( id + id)
根据左推导定义，有
E => - E => - ( E ) => - ( E + E ) => - ( id + id )
语法树
最左推导
最右推导
定义
在最右推导中，总是选择每个句型的最右非终结符号。
例子
有文法：
E -> E +E | E * E | - E | ( E ) | id
需要推出串 - ( id + id)
根据左推导定义，有
E => - E => - ( E ) => - ( E + E ) => - ( id + id )
语法树
最右推导
