学习编译原理Time05 ~ 文法的认知
<句子> → <名词短语><动词短语>
<名词短语>→<形容词><名词短语>
<名词短语>→<名词>
<动词短语>→<动词><名词短语>
<形容词>→big
<名词>→boy
<名词>→apple
<动词>→eat
上面未用尖括号括起来部分表示语言的基本符号
尖括号括起来部分称为语法成分
文法的形式化定义
G=（VT，VN，P，S）
VT：终结符集合
终结符(terminal symbol)是文法所定义的语言的基本符号，有时也称为token。
例：VT={apple, boy, eat,big }
VN：非终结符集合
非终结符集合(nonterminal)是用来表示语法成分的符号，有时也称为”语法变量”
例：VN={<句子>，<名词短语>，<动词短语>，<名词>，...}
在这个要注意一下，VT和VN这两个集合是不相交的。VT和VN并起来统称文法符号集
P：产生试集合
产生式（production）描述了将终结符和非终结符组合成串的方法，一般形式为：α →β，读作α定义为β。
α
(VT U VN)+, 且α中至少包含VN中的一个元素：称为产生式的头(head)或左部(leftside)
VT、VN 两个字母表并起来也是一个字母表，上一篇文章也说到，字母表的闭包是是这个字母表的字符串构成的集合，因此α和β为文法符号串。
β(VT U VN)*: 称为产生式的体(body)或右部(right side)
例：P={<句子> → <名词短语><动词短语>，
<名词短语>→<形容词><名词短语>，
......
}
S：开始符号
SVN ，开始符号(start symbol)表示的是该文法中最大的语法成分。
例：S=<句子>
下面来看一下文法的例子
G=（{id，+，*，(, ) }，{E}，P，E）
P={E→E+E,
E→E*E,
E→(E),
E→id }
产生式的简写
对一组由相同左部的α产生式
α →β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 |
为了说明哪些是终结符，哪些是非终结符，这里进行符号约定
下面符号是终结符：
字母表中排在前面的小写字母，如a，b，c
运算符，如+、*等
标点符号，如逗号，括号等
数字0，1，2、...、9
粗体字符串，如id，if等
下面符号是非终结符：
字母表中排在前面的大写字母，如A，B，C
字母S。通常表示开始符号
小写、斜体的名字，如expr、stmt等
代表程序构造的大写字母。如E(表达式)、T(项)和F(因子)
字母表中排在后面的大写字母(如X、Y、Z）
表示文法符号（即终结符或非终结符）
字母表中排在后面的小写字母(主要是u、v、...、z）
表示终结符号串（包括空串）
小写希腊字母，如α 、β、γ，表示文法符号串（包括空串）
除非特别说明，第一个产生式的左部就是开始符号
小浩笔记
