《编译原理》求短语 直接短语 句柄 素短语 最左素短语 - 例题解析

《编译原理》求短语，直接短语，句柄，素短语，最左素短语 - 例题解析

笔记

（一）明确概念：

例题1：求短语，直接短语，句柄

给定句型：

T*P↑(T*F)

给定文法：

G[T]:

T → T*F|F

F → F↑P|P

P → (T)|i

解析：

推导步骤为：

T ⇒ T*F

⇒ T*F↑P

⇒ T*P↑P

⇒ T*P↑(T)

⇒ T*P↑(T*F)

画出语法树为：

该语法树的 5 个子树及 5 个短语为：

求直接短语方法：该句型的语法树有两颗直接子树（最左边的两颗子树），由这两颗直接子树的叶子结点组成的符号串（或者说只包含两层的子树叶子结点对应的），就是句型的两个直接短语，直接短语 P 和 T*F。

求句柄：因为 P 相对 T*F，在语法树上的左侧，所以句柄是 P

最终结果：

例题二：求素短语，最左素短语

给定句型：

FF↑*a*

给定文法：

G[T]:

T → T*F|F

F → F↑P|P

P → (T)|i

解析：

推导步骤为：

T ⇒ TF*

⇒ TF*F*

⇒ TF↑*\F*

⇒ TF↑*a*

画出语法树：

最终结果：

根据定义可以找出素短语有：