1、文法制導翻譯
--------------------------------------
(1)文法制導翻譯(SDTS)直覺上就是為每個産生式配上一個翻譯子程式(稱之為予以動作或者
語義子程式)，并且在執行文法分析的時候執行這些子程式。
(2)文法分析過程中，當一個産生式獲得比對(對于自上而下的分析)或用于規約(對自下而上
的分析)時，産生式相應的語義子程式進入工作完成既定的任務。
(3)示例1：
* 【題目】令S.val為文法G[S]生成的二進制數的值，例如對輸入串101.101，則
S.val=5.625。按照文法制導翻譯方法的思想，給出計算S.val的相應的語義
規則，G(S)如下：
G[S]: S→L.L|L
L→LB|B
B→0|1
*【解答】計算S.val的文法G′[S]及語義動作如下：
産生式 語義動作
G′[S]：S′→S {print(S.val)}
S→L1·L2 {S.val:=L1.val + L2.val/2L2.length}
S→L {S.val:=L.val}
L→L1B {L.val:=L1.val*2 + B.val
L.length:=L1.length +1}
L→B {L.val:=B.val L.length:=2}
B→1 {B.val:=1}
B→0 {B.val:=0}
2、逆波蘭表示法
----------------------------------
(1)如果E是變量或者常數，則E的字尾為其本身;
(2)如果E為 E1 op E2的形式，則其字尾表示為 E1'E2'op;
(3)如果E的形式為(E),則與E的字尾表示相同。
(4)字尾表達方式中，操作數的出現順序是相同的。
(5)示例
【題目】有一文法制導翻譯如下所示:
S→bAb {print″1″}
A→(B {print″2″}
A→a {print″3″}
B→Aa) {print″4″}
若輸入序列為b(((aa)a)a)b，且采用自下而上的分析方法，求輸出序列。
【解答】當采用自上而下的方式來構造其文法樹時，如下：
S
/ | \
b A b 1 //(((aa)a)a)
/ \
( B 2 //((aa)a)a)
/|\
A a ） 4 //((aa)a)
/ \
( B 2 //(aa)a)
/|\
A a ) 4 //(aa)
/ \
（ B 2 //aa)
/|\
A a ) 4 //a
|
a 3 //
這裡題目采用的是自下而上的分析方式，則其輸出序列為34242421
3、編譯原理的基本概念
-------------------------------------
(1)編譯程式是将進階語言的源程式作為輸入并轉化為低級語言的目标代碼的程式。
(2)編譯程式是将進階語言轉化為低級語言，低級語言包括彙編語言和及其語言，而
彙程式設計式則是将彙編語言轉化為機器語言。
(3)解釋程式與編譯程式的差別是解釋程式逐行讀取源程式并執行，這個過程中不會
産生目标代碼。解釋程式在執行速度上比編譯的慢，但是人機互動界面要好。
(4)源程式是指用進階語言書寫的程式，而目标程式是指計算機所能識别的機器代碼。
(5)編譯過程：詞法分析、文法分析、語義分析與中間代碼生成、優化與目标代碼生成。
以及貫穿整個過程的表格管理和出錯處理。
(6)一個編譯任務可以分為很多遍來完成，其中完成某些特定的功能稱之為一遍。
(7)自編譯是指使用進階語言來寫自己的編譯器。
(8)交叉編譯是指在A機器上開發運作與B機器上的編譯器。
(9)自展是先定義好一個核心的簡單語言L0，用彙編語言或者機器語言書寫這個簡單語言
L0的編譯器T0，然後将L0擴充為L1，使用自編譯的方式用L0來書寫L1的編譯器T1，這樣
不斷地進行擴充直到滿足所有的功能為止。
(10)移植是指在A機器上運作的程式隻要稍加改動就可以在B機器上運作。
4、詞法分析的基本概念
--------------------------------------
(1)詞法分析接收的輸入是源程式代碼，輸出的是單詞符号串。
(2)詞法分析的兩種組織形式：
一是将詞法分析作為單獨的一遍來進行。
二是将詞法分析作為文法分析的一個子程式來進行。
(3)掃描器即詞法分析器。
(4)單詞是最小的具有明确語義的文法機關。
(5)詞法分析器輸出的單詞采用二進制組進行儲存，即(單詞種别，單詞自身的值)。
(6)單詞的分類：保留字，辨別符，常量，運算符和界符。
(7)狀态轉換圖，即表示不同的輸入下的狀态之間的轉換。
5、正規表達式
--------------------------------------
(1)正規表達式是一種形式化的表示方法，表示單詞符号的結構，進而精确地定義單詞集。
(2)運算規則
-- 給定字母表Z
-- e和q是Z上的一個正規式，則其正規集分别為{e}{q}。
-- 對任意a屬于Z，a的正規式為 {a}
-- 若S和R是Z上的正規式，對其正規集L(R)和L(S），有：
R|S是Z上的正規式，其正規集為 L(R)UL(S)
R·S是Z上的正規式，其正規集為L(R)L(S)
(R)*是Z上的正規式，其正規集為(L(R))*
-- 任何正規式都有正規集 E
-- R|S = S|R
(3)示例：
【例2.1】令Z={a,b},R=a(a|b)*是Z上的正規式，求R的正規集。
【解答】L(R) = L(a(a|b)*)
= L(a)L((a|b)*）
= L(a)(L(a)UL(b))*
={a}{a,b}*
={e,a,aa,ab,aaa,aab,...}
【例2.2】判斷下列正規式是否等價
(a|b)*與a*|b* (ab)*與a*b* (a|b)*與（a*b*）*
【解答】
(1)L((a|b)*)表示任意有a和b組成的字母串
L(a*|b*)表示任意a在b前的字母串，是以不等價
(2)L((ab)*)={e，ab,abab,ababab,...}
L(a*b*) ={e,a,b,aa,ab,aaa,aab,...}是以不等價
(3)L((a|b)*)= {a,b}* = {e,a,aa,ab,aaa...}
L((a*b*)*)=({a}*{b}*)*={e,a,aa,ab,aaa...}是以等價
【例2.3】證明L(a+) = {a}* -{e}
【解答】
L(a+) = {a*} - {e}
= {e,a,aa,aaa,...}-{e}
= {a,aa,aaa,...}
= {a}{e,a,aa,aaa,...}
= L(aa*)
是以 a+ = aa*
【習題2.4】正規式(ab)*a與正規式a(ba)*是否等價？請說明理由。
【解答】
L((ab)*a)與L(a(ba)*)的最簡NFA相同，是以等價。
6、有限自動機
--------------------------------------
(1)表示方法：五元組(S,Z,f,S0,z)
S:狀态集
Z:字母表
f:映射關系
s0:初态
z：終态
(2)确定有限自動機DFA:f為單值映射
(3)非确定有限自動機NFA：f為多值映射
(4)狀态轉換圖和狀态轉換矩陣
【例題2.4】假定DFA Md=({s0,s1,s2},{a,b},f,s0,{s2})：
f:
f(s0,a) = s1 f(s0,b) = s2
f(s1,a) = s1 f(s1,b) = s2
f(s2,a) = s2 f(s2,b) = s1
試着給出Md的狀态轉換圖和狀态轉換矩陣。
【解答】
狀态轉化圖略
狀态轉換矩陣如下
a b
s0 s1 s2
s1 s1 s2
s2 s2 s1
【例題2.5】假定NFA Md=({s0,s1,s2},{a,b},f,{s0,s2},{s1})有：
f:
f(s0,a) = {s2} f(s0,b) = {s0,s1}
f(s1,a) = null f(s1,b) = {s2}
f(s2,a) = null f(s2,b) = {s1}
試着給出Md的狀态轉換圖和狀态轉換矩陣。
【解答】
狀态轉換矩陣如下：
a b
s0 {s2} {s0, s2}
s1 - {s2}
s2 - {s1}
【習題2.5】設有L(G)={a2n+1b2ma2p+1| n≥0,p≥0,m≥1}
(1) 給出描述該語言的正規表達式；
(2) 構造識别該語言的确定有限自動機(可直接用狀态圖形式給出)。
【解答】
(1)a(aa)*bb(bb)*a(aa)*
(2)畫出狀态轉換圖、寫出狀态轉換矩陣、重命名、确定化NFA
【習題2.6】對給定的表達式b*(d|ad)(b|ab)+構造其NFA M
7、NFA的确定化及其化簡
---------------------------------------------
(1)采用子集法确定化NFA
首先定義FAM的一個狀态子集I的e_閉包，即e_closure(I),
若si 屬于 I ，則si 包含于 e_閉包
若si 屬于 I ，則從si出發經過e通路所能到達的任何狀态sj，都有sj包含于e_閉包。
Ia表示從某一狀态出發經過有向邊a而能到達的狀态集。
(2)确定化方法
*構造一張轉換表，第一列為狀态子集I，對不同的a屬于Z單設一列Ia
*表的第一行第一類為I的e_閉包(s0)，其中s0為初始狀态。
*為每一個新産生的狀态添加一行，直到沒有新的狀态出現為止
*重命名表格
(3)确定化DFA的化簡
*将DFA的狀态集劃分為終點集合非終點集。
*對非終點集中的狀态逐一檢查
【例2.8】正規表達式(a|b)*(aa|bb)(a|b)*的NFA M如圖所示，試着确定化DFA M'
【解答】
(1)由狀态轉換圖得：
I Ia Ib
{X,1,2} {1,2,3} {1,2,4}
{1,2,3} {1,2,3,5,6,Y}{1,2,4}
{1,2,4} {1,2,3} {1,2,4,5,6,Y}
{1,2,3,5,6,Y}{1,2,3,5,6,Y}{1,2,4,6,Y}
{1,2,4,5,6,Y}{1,2,3,6,Y} {1,2,4,5,6,Y}
{1,2,4,6,Y} {1,2,3,6,Y} {1,2,4,5,6,Y}
{1,2,3,6,Y} {1,2,3,5,6,Y}{1,2,4,6,Y}
(2)重新命名得：
I Ia Ib
0 1 2
1 3 2
2 1 4
3 3 5
4 6 4
5 6 4
6 3 5
(3)重新繪制狀态圖 DFA M
【例2.9】化簡2.8中的DFA M’
【解答】
(1)終态集為{3,4,5,6},非終态集為{0,1,2}
(2)對非終态集{0,1,2}a進行考察，其中
{0}a = {1}
{2}a = {1}
{1}a = {3} 分别屬于終态集合非終态集，故劃分為{0,2}和{1}
(3)對{0,2}b進行考察
{0}b = {2}
{2}b = {4} 分别屬于非終态集和終态集，故劃分為{0}和{2}
(4)對終态集{3,4,5,6}a進行考察
{3}a = {3}
{4}a = {6}
{5}a = {6}
{6}a = {3}
(5)對終态集{3,4,5,6}b進行考察
{3}b = {5}
{4}b = {4}
{5}b = {4}
{6}b = {5} 故不進行劃分
(6)重新命名{0},{1},{2},{3,4,5,6}為0,1,2,3，得到化簡後的矩陣
I Ia Ib
0 1 2
1 3 2
2 1 3
3 3 3
(7)重新繪制狀态轉換圖，得到化簡後的DFA M'
【例2.10】使用DFA的等價性證明正規表達式(a|b)*與(a*b*)*等價
【解答】
(1)畫出兩者的狀态轉換圖
(2)寫出狀态轉換表
(3)重命名狀态轉換表得到狀态轉化矩陣
(4)化簡狀态轉化矩陣
(5)得到最終的化簡後的DFA
【例2.13】已知Z={a,b},求以字元串中每個a都直接至少有一個b跟在其後面。
(1)确定其正規表達式為：b*(abb*)*
(2)畫出其狀态圖
(3)畫出其狀态轉換表
(4)重命名得到狀态關系矩陣
(5)化簡矩陣
(6)得到DFA M’
【習題2.6】有語言L={w | w<-(0,1)+},并且w中至少有兩個1，又在任何兩個1
之間有偶數個0}，試着構造其有限狀态自動機DFA。
【解答】
(1）确定其正規表達式為：0*1(00(00)*1)*(00)(00)*1*0
(2) 畫出其狀态轉化圖
(3) 畫出其狀态轉化表
(4) 重命名得到狀态轉換矩陣
(5) 化簡
(6) 得到确定化的DFA
8、文法分析基本概念
-----------------------------------------
(1)語言：對于字母表Z的所有集合Z*的一個子集稱為Z上的一個語言。
(2)語句：對于語言中的沒一個字元串稱之為語句。
(3)文法：文法通常用四元組組成，G[S]=(Vt，Vn，S，s);
Vt表示非終結符
Vn表示終結符
S是一個特殊的非終結符，是我們所關注的文法開始符
s表示産生式集合。
(4)終結符：語言中不可再分的基本符号。
(5)開始符：是我們關注的文法實體，即語言的目标。
(6)産生式：是定義文法實體的一種書寫規則。
(7)句型：文法G[S]中有S =*=> a,則a是文法G的一個句型。
(8)句子：文法G[S]中有S =*=> a,且a屬于終結符，則a是文法G的一個句子。
(9)最左推導：每次都對句型的最左非終結符開始進行推導。
(10)最右推導：每次都對句型的最右非終結符進行推導。
(11)短語：asp是文法G[s]的一個句型，若有A=+=>s,則s是A的一個短語。
(12)直接短語：隻推導一次的短語
(13)句柄：一個句型的最左直接短語。
(14)素短語：含有終結符的短語。而且不存在具有相同性質的真子串。
(15)文法的二義性：如果一個文法産生多個文法樹，則是二義性的。
【例3.1】構造産生辨別符的文法
【解答】
辨別符有字母開頭，有字母和數字組成的字母數字串。
(1)定義字母集： D--> a|b|c|...|z
(2)定義數字集： L--> 0|1|2|...|9
(3)定義字母或數字： T --> L|D
(4)定義字母數字串： S --> T|ST
(5)定義辨別符： I --> L|LS
故産生的文法G[I]為：
G[I]=({0,1,...a,b,..z},{D,L,T,S,I},I,s)
s:
I --> L|LS
S --> T|ST
T --> L|D
D --> a|b|c|..|z
L --> 0|1|2|3|...|9
【例3.2】寫一個文法使其語言是奇數集合，但不允許出現以0開頭的奇數
【解答】
(1)定義最高位：F --> 1|2|3|...|9
(2)定義最低位：B --> 1|3|5|7|9
(3)定義中間部分：M --> 0|1|2|...|9
(4)定義非最低位：S --> F|FM
(5)定義非零開頭的奇數: I --> S|SB
故産生的文法為：
G[I] = ({0,1,2,...9},{F,B,M,S,I},I,s)
s：
I --> S|SB
S --> F|FM
M --> 0|1|2|...|9
B --> 1|3|5|7|9
F --> 1|2|...|9
9、文法的分類
----------------------------------------------
(1)0型文法: a-->b,其中a 至少含有一個非終結符，識别的系統是圖靈機。
(2)1型文法: aAb --> acb,上下文有關文法，A隻有在上下文中才可以被替換。
(3)2型文法: A --> a 其中a是終結符
(4)3型文法: A --> a 或 A --> aB
(5)四種文法的差別與聯系
*從0--3文法逐漸加強
*1-3型文法屬于0型文法
*2-3 不一定屬于1型文法
*1型文法中不允許出項 A-->a的情況
*0、1型文法的産生式左部含有終結符号的符号串或者兩個及兩個以上的非終結符。
*2、3型文法的産生式左部隻允許出現單個的非終結符。
【例3.4】給出字母表Z={a,b}上同時隻有奇數個a和奇數個b的所有字元串集合的正規
文法。
【解答】
(1)畫出該正規文法的DFA
(2)定義産生式集合s
S --> aA|bB
A --> aS|bC|b
B --> bS|aC|a
C --> bA|aB|e
(6)二義性文法的消除
*消除左遞歸
*消除回溯
【習題3.3】已知文法G[S]為S→aSb|Sb|b，試證明文法G[S]為二義文法。
【解答】
構造出兩棵不同的文法樹即可。
【習題3.4】已知文法G[S]為S→SaS|ε，試證明文法G[S]為二義文法。
【解答】構造出兩棵不同的文法樹即可。
【習題3.6】有文法G[S]: S→aAcB|Bd
A→AaB|c
B→bScA|b
(1) 試求句型aAaBcbbdcc和aAcbBdcc的句柄；
(2) 寫出句子acabcbbdcc的最左推導過程。
【解答】
(1)構造其分析文法樹
s
/ / \ \
a A c B
/|\ / | | \
A a B b S c A
/ \ |
B d c
|
b 是以句柄為AaB
s
/ / \ \
a A c B
/ / \ \
b S c A
/ \ |
B d c 是以句柄為Bd
(2)acabcbbdcc
S
/ / \ \
a A c B
/|\ \ \ \ \
A a B b S c A
| | /\ |
c b B d c
|
b
是以推導過程為：S aAcB aAaBcB acaBcB acabcB acabcbScA
acabcbBdcA acabcbbdcA acabcbbdcc
【習題3.7】對于文法G[S]: S→(L)|aS|a
L→L,S|S
(1) 畫出句型(S,(a))的文法樹；
(2) 寫出上述句型的所有短語、直接短語、句柄、素短語和最左素短語。
【解答】
(1)
S
/ | \
( L )
/|\
L , S
| / | \
S ( L )
|
S
|
a
(2)短語：S，a，（a），S,(a),(S,(a))
直接短語：a,S
句柄： S
素短語：a
最左素短語：a
11、LL(1)分析法：預測分析法
--------------------------------------------------
(1)第一個L表示自頂向下、自左向右掃描輸入串。第二個L表示分析過程中使用
最左推導。1表示向右檢視一個符号就可以決定如何推導。
(2)輸入串是待分析的符号串，以界符#作為結束标志。由程式自動生成。
(3)分析棧中存放文法符号，剛開始存放一個#，當輸入串的指針也指向#時，分析成功。
(4)LL(1)分析表的構造
First集合：a是文法G[s]的一符号串，First(s)={a|s=*=>a,a屬于非終結符}
Follow集合：Follow(a)={a|S*=>...Aa...}
(5)若X-->a... 則a屬于First(X)。
若X-->Y... 則{First(Y)-e}屬于First(X)。
若A-->aBb 則{First(b)-e}屬于Follow(B)。
(6)LL(1)中的First(A)與Follow(A)相交為空。
【例3.7】下面是LL(1)分析表，試對輸入串aadl的分析過程。
a b l d #
A A->aA'
A' A'->ABl A'->e A'->e
B B ->dB'
B' B'->bB' B'->e
【解答】
符号棧 目前符号 輸入串
#A a adl#
#A'a a adl#
#A' a dl#
#lBA a dl#
#lBA'a a dl#
#lBA' d l#
#lB d l#
#lB'd d l#
#lB' l #
#l 1 #
# #
【習題3.10】已知文法G[A]: A→aABl|a
B→Bb|d
(1) 試給出與G[A]等價的LL(1)文法G[A′]；
(2) 構造G[A′]的LL(1)分析表；
(3) 給出輸入串aadl#的分析過程。
【解答】
(3)符号棧 目前符号 輸入串
#A a adl#
#A'a a adl#
#A' a dl#
#lBA a dl#
#lBA'a a dl#
#lBA' d l#
#lB d l#
#lB'd d l#
#lB' l #
#l 1 #
# #
【習題3.2】令文法G[N]為
G[N]: N→D|ND
D→0|1|2|3|4|5|6|7|8|9
(1) G[N]的語言L(G[N])是什麼?
(2) 給出句子0127、34和568的最左推導和最右推導。
【解答】
(1)非負整數
(2)NND NDD NDDD DDDD 0DDD 01DD 012D 0127
N ND N7 ND7 N27 ND27 N127 D127 0127
【習題3.13】設有文法G[S]: S→a|b|(A)
A→SdA|S
(1) 構造算符優先關系表；
(2) 給出句型(SdSdS)的短語、簡單短語、句柄、素短語和最左素短語；
(3) 給出輸入串(adb)#的分析過程。
【解答】
(3)符号棧 輸入串 說明
# (adb)# 移進
#( adb)# 移進
#(a db)# S-->a規約
#(S db)# 移進
#(Sd b)# 移進
#(Sdb )# S-->b進行規約
#(SdS )# 移進
#(SdA )# A-->S進行規約
#(A )# 移進
#(A） )# S-->(A)進行規約
#S # 分析成功
【習題3.25】給出文法G[S]及圖3-16所示的LR(1)項目集規範族中的0、1、2、3、4。
G[S]: S→S;B | B
B→BaA | A
A→b(S)
12、算符優先分析法
--------------------------------------
(1)算符優先是一種自底向上的分析方法。
(2)所謂算符優先，就是依照算數表達式的四則運算過程來進行文法分析。即這種分析方法
要預先規定運算符之間的優先關系和綜合性質，然後借助這個關系來确定句型的可規約
來進行規約。
(3)任何産生式的右部都不含兩個并列的非終結符的文法為算符文法。
(4)若P->...aB... B=+=>b 則 a<b
若P->...Ab... A=+=>a 則 a>b
若P->...ab... 則 a=b
(5)文法G[s]中任何一個産生式的右部都不含相鄰的兩個終結符，即為算符文法。而算符
優先文法中存在明确的算符優先順序。在文法樹上，下層的算符的優先級比上層的算
符的優先級高。
(6)若P->a...或者P->Qa... 則a屬于FirstVt(P);
若P->Q... 則FirstVt(Q)包含于FirstVt(P)
(7)若有産生式P->...a或者P->...aQ 則a屬于LastVt(P)
若有産生式P->...Q 則LastVt(Q)包含于LastVt(P)
【例3.11】說明下列文法是否是一個算符優先文法。
G[E]:E->E+E|E*E|(E)|i
【解答】
(1)首先文法中的任何一個産生式都不存在兩個相鄰的非終結符，是以屬于算符
文法。
(2)有E->E+E,第二個E可以推出E->E*E,是以+<*
在E->E+E,第一個E可以推出E->E*E,是以*<+
是以不是算符優先算法。
【例3.12】構造下列文法的算符優先關系表
G[E]: E->E+T|T
T->T*F|F
F->(E)|i
【解答】
(1)由E->+....|E->i,是以FirstVt(E) = {+,i}
(2)由T->*....,是以FirstVt(T)={*}
(3)由F->(....|i,是以FirstVt(F)={(,i}
(4)由E->T,是以FirstVt(T)屬于FirstVt(E),是以FirstVt(E)={+,i,*,(}
(5)由T-<F,是以FirstVt(F)屬于FirstVt(T),是以FirstVt(T)={*,(,i}
(6)由E-> ...+T,是以LastVt(E)={+}
(7)由T-> ...*F,是以LastVt(T)={*}
(8)由F-> ...)|i,是以LastVt(F)={),i}
(9)由T->F,是以LastVt(F)包含于LastVt(T),是以LastVt(T)={*,),i}
(10)由E->T,是以LastVt(T)包含于LastVt(E),是以LastVt(E)={+,*,),i}
(11)由E->(E),是以 （ = ）
(12)由E->...+T,是以，+ < FirstVt(T)
(13)由E->...*F,是以，* < FirstVt(F)
(14)由E->E+...,是以，+ < LastVt(E)
(15)由E->T*...,是以 * < LastVt(T)
(16)由F->(E...,是以 （ < FirstVt(E)
(17)由F-> E)..,是以 ）< LastVt(E)
+ * i ( ) #
+ > < < < > >
* > > < < > >
i > > > >
( < < < < =
) > > > >
# < < < < =
【例3.14】輸入串i+i*i的分析過程，算符優先算法
【解答】
符号棧 輸入串 動作
# i+i*i# #<i
#i +i*i# #<i>+用F->i規約
#F +i*i# #<+
#F+ i*i# #<
...
[詞法分析]
詞法分析從左向右掃描每行源程式的符号，按照詞法規則，從構成源程式的字元串中識别
出一個個具有獨立意義的最小文法機關，并轉換成同意的内部表示，送給文法分析程式。
[LL(1)文法]
若檔案的任何兩個産生式 A--> a|b都滿足下面兩個條件
(1)First(a)交First(b)為空集
(2)若b經過若幹步驟可以推導為e(空集)，那麼First(a)交Follow(A)為空集。
第一個L表示從左向右進行掃描，第二個L表示最左推導。1表示決定分析器的每個
動作時向前看一個輸入符号。沒有公因子，不是二義性的，也不含左遞歸。
[文法樹]
句子的樹結構表示法稱為文法樹(文法分析樹或文法推導樹)。
給定文法G=(VN，VT，P，S)，對于G的任何句型都能構造與之關聯的
文法樹。這棵樹具有下列特征：
(1)根節點的标記是開始符号S。
(2)每個節點的标記都是V中的一個符号。
(3)若一棵子樹的根節點為A，且其所有直接子孫的标記從左向右的排列
次序為A1A2…AR，那麼AA1A2…AR一定是P中的一條産生式。
(4)若一标記為A的節點至少有一個除它以外的子孫，則A VN。
(5)若樹的所有葉節點上的标記從左到右排列為字元串w，則w是文法G
的句型；若w中僅含終結符号，則w為文法G所産生的句子。
[LR(0)分析器]
所謂LR(0)分析，是指從左至右掃描和自底向上的文法分析，且在分析的
每一步，隻須根據分析棧目前已移進和歸約出的全部文法符号，并至多再
向前檢視0個輸入符号，就能确定相對于某一産生式左部符号的句柄是否
已在分析棧的頂部形成，進而也就可以确定目前所應采取的分析動作 (是
移進還是按某一産生式進行歸約等)。
[語言和文法]
文法就是語言結構的定義和描述，是有窮非空的産生式集合。
文法G定義為四元組的形式：
G=(VN，VT，P，S)
其中：VN 是非空有窮集合，稱為非終結符号集合；VT 是非空有窮集合，
稱為終結符号集合；P是産生式的集合(非空)；S是開始符号(或識别符号)。
這裡，VN∩VT=，S VN。V=VN∪VT，稱為文法G的字母表，它是出現
文法産生式中的一切符号的集合。
文法G所描述的語言用L(G)表示，它由文法G所産生的全部句子組成，即
L(G)={x| SÞ*x，其中S為文法開始符号，且 }
簡單的說，文法描述的語言是該文法一切句子的集合。
![編譯器"自舉與移植"原理[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)