网站建设siteserver今朝装饰

写在最前
本文为编译原理重点考察大题之一，理论基础见专栏文章，0基础直接使用也可食用

推导构造语法树

1.语法树的概念

推导过程用图表示，即为语法树，也叫推导树
语法树是一棵有序有向树
推导过程不同，生成语法树的过程也不同，但最终生成的语法树是相同的。

给出一棵语法树的例子：

注意每一个符号都不要落下，按照推导过程构造语法树

2. 子树，短语，简单短语，句柄

2.1 子树

子树就是以树的某个结点为根，连同他全部的后裔组成。

如上小节给出语法树中，包含根节点S，S1，S2，S3，S4的五棵子树

注意叶子结点不算子树

2.2 短语

短语是相对一个句型的，一个句型对应多个短语。
短语就是该句型子树的叶子结点

如何寻找一个句型短语？
1️⃣画出句型语法树
2️⃣找出所有子树
3️⃣子树叶子结点组成的符号串为该句型针对子树根节点的短语
4️⃣去掉重复的短语

找短语的关键还是找子树

2.3 简单短语与句柄

所有短语中，一步推导得来的即为简单短语。
最左边的简单短语就是该句型的句柄。

2.4 真题实战

题目一：

左图答案：
短语：aa+a* ，aa+，a
简单短语：a
句柄：a

右图答案：
短语 abccdd，ab，ccdd，cd
直接短语：ab，cd
句柄：ab

题目二：
已知文法G[E]:E→ET+|T , T→TF*|F , F→F^|a
求证FF^^*是文法的句型，指出短语，简单短语和句柄