寫在最前
本文為編譯原理重點(diǎn)考察大題之一，理論基礎(chǔ)見專欄文章，0基礎(chǔ)直接使用也可食用

推導(dǎo)構(gòu)造語法樹

1.語法樹的概念

推導(dǎo)過程用圖表示，即為語法樹，也叫推導(dǎo)樹
語法樹是一棵有序有向樹
推導(dǎo)過程不同，生成語法樹的過程也不同，但最終生成的語法樹是相同的。

給出一棵語法樹的例子：

注意每一個(gè)符號(hào)都不要落下，按照推導(dǎo)過程構(gòu)造語法樹

2. 子樹，短語，簡(jiǎn)單短語，句柄

2.1 子樹

子樹就是以樹的某個(gè)結(jié)點(diǎn)為根，連同他全部的后裔組成。

如上小節(jié)給出語法樹中，包含根節(jié)點(diǎn)S，S1，S2，S3，S4的五棵子樹

注意葉子結(jié)點(diǎn)不算子樹

2.2 短語

短語是相對(duì)一個(gè)句型的，一個(gè)句型對(duì)應(yīng)多個(gè)短語。
短語就是該句型子樹的葉子結(jié)點(diǎn)

如何尋找一個(gè)句型短語？
1??畫出句型語法樹
2??找出所有子樹
3??子樹葉子結(jié)點(diǎn)組成的符號(hào)串為該句型針對(duì)子樹根節(jié)點(diǎn)的短語
4??去掉重復(fù)的短語

找短語的關(guān)鍵還是找子樹

2.3 簡(jiǎn)單短語與句柄

所有短語中，一步推導(dǎo)得來的即為簡(jiǎn)單短語。
最左邊的簡(jiǎn)單短語就是該句型的句柄。

2.4 真題實(shí)戰(zhàn)

題目一：

左圖答案：
短語：aa+a* ，aa+，a
簡(jiǎn)單短語：a
句柄：a

右圖答案：
短語 abccdd，ab，ccdd，cd
直接短語：ab，cd
句柄：ab

題目二：
已知文法G[E]:E→ET+|T , T→TF*|F , F→F^|a
求證FF^^*是文法的句型，指出短語，簡(jiǎn)單短語和句柄