學(xué)習(xí)編譯原理Time05 ~ 文法的認(rèn)知
<句子> → <名詞短語><動(dòng)詞短語>
<名詞短語>→<形容詞><名詞短語>
<名詞短語>→<名詞>
<動(dòng)詞短語>→<動(dòng)詞><名詞短語>
<形容詞>→big
<名詞>→boy
<名詞>→apple
<動(dòng)詞>→eat
上面未用尖括號(hào)括起來部分表示語言的基本符號(hào)
尖括號(hào)括起來部分稱為語法成分
文法的形式化定義
G=（VT，VN，P，S）
VT：終結(jié)符集合
終結(jié)符(terminal symbol)是文法所定義的語言的基本符號(hào)，有時(shí)也稱為token。
例：VT={apple, boy, eat,big }
VN：非終結(jié)符集合
非終結(jié)符集合(nonterminal)是用來表示語法成分的符號(hào)，有時(shí)也稱為”語法變量”
例：VN={<句子>，<名詞短語>，<動(dòng)詞短語>，<名詞>，...}
在這個(gè)要注意一下，VT和VN這兩個(gè)集合是不相交的。VT和VN并起來統(tǒng)稱文法符號(hào)集
P：產(chǎn)生試集合
產(chǎn)生式（production）描述了將終結(jié)符和非終結(jié)符組合成串的方法，一般形式為：α →β，讀作α定義為β。
α
(VT U VN)+, 且α中至少包含VN中的一個(gè)元素：稱為產(chǎn)生式的頭(head)或左部(leftside)
VT、VN 兩個(gè)字母表并起來也是一個(gè)字母表，上一篇文章也說到，字母表的閉包是是這個(gè)字母表的字符串構(gòu)成的集合，因此α和β為文法符號(hào)串。
β(VT U VN)*: 稱為產(chǎn)生式的體(body)或右部(right side)
例：P={<句子> → <名詞短語><動(dòng)詞短語>，
<名詞短語>→<形容詞><名詞短語>，
......
}
S：開始符號(hào)
SVN ，開始符號(hào)(start symbol)表示的是該文法中最大的語法成分。
例：S=<句子>
下面來看一下文法的例子
G=（{id，+，*，(, ) }，{E}，P，E）
P={E→E+E,
E→E*E,
E→(E),
E→id }
產(chǎn)生式的簡寫
對一組由相同左部的α產(chǎn)生式
α →β1，α →β2，...，α →βn
可以簡記為：α →β1| β2 |...| βn。
讀作：α定義為β1，....,或者βn
β1，β2，...，βn稱為α 的候選式(Candidate)
例：
E→E+E, E→E*E, E→(E), E→id | → | E→E+E | E*E | (E) | id |
為了說明哪些是終結(jié)符，哪些是非終結(jié)符，這里進(jìn)行符號(hào)約定
下面符號(hào)是終結(jié)符：
字母表中排在前面的小寫字母，如a，b，c
運(yùn)算符，如+、*等
標(biāo)點(diǎn)符號(hào)，如逗號(hào)，括號(hào)等
數(shù)字0，1，2、...、9
粗體字符串，如id，if等
下面符號(hào)是非終結(jié)符：
字母表中排在前面的大寫字母，如A，B，C
字母S。通常表示開始符號(hào)
小寫、斜體的名字，如expr、stmt等
代表程序構(gòu)造的大寫字母。如E(表達(dá)式)、T(項(xiàng))和F(因子)
字母表中排在后面的大寫字母(如X、Y、Z）
表示文法符號(hào)（即終結(jié)符或非終結(jié)符）
字母表中排在后面的小寫字母(主要是u、v、...、z）
表示終結(jié)符號(hào)串（包括空串）
小寫希臘字母，如α 、β、γ，表示文法符號(hào)串（包括空串）
除非特別說明，第一個(gè)產(chǎn)生式的左部就是開始符號(hào)
小浩筆記
