Part 2
Language Description and
Implementation
语言描述与实现程序语言的定义
程序语言由两方面定义：
语法
语义
语用教学要点
上下文无关文法
直接推出与推导、最左推导与最右推导
句型、句子与语言
递归与语言
语法树与二义性
EBNF与语法图
乔姆斯基文法一,语法
程序本质上是一定字符集上的 字符串 。
语法,一组规则,用它可以形成和产生一个合式 (well-formed)的程序 。
语 法
词法规则,单词符号的形成规则 。
单词符号是语言中具有独立意义的最基本结构 。 一般包括：常数、标识符、基本字、算符、界符等。
描述工具：有限自动机
语法规则,语法单位的形成规则 。
语法单位通常包括：表达式、语句、分程序、过程、函数、程序等 ;
描述工具：上下文无关文法
G1,E→i
E→E+E
E→E*E
E→(E)
语法规则和词法规则定义了程序的的形式结构。定义语法单位的意义属于语义问题。
二,语义
语义,一组规则,用它可以定义一个程序的意义 。
描述方法：
自然语言描述：隐藏错误、二义性和不完整性
形式描述：
操作语义
指称语义
代数语义
2.1 程序语言的语法描述
几个概念,
考虑一个 有穷 字母表 ∑ 字符集
其中每一个元素称为一个 字符
∑ 上的 字 (也叫 字符串 ) 是指由 ∑ 中的字符所构成的一个有穷序列
不包含任何字符的序列称为 空字,记为 ε
用 ∑ *表示 ∑ 上的所有字的全体,包含空字 ε
例如,设 ∑ ={a,b}，则
∑ *={ε,a,b,aa,ab,ba,bb,aaa,...}
∑*的子集 U和 V的 连接 （ 积 ） 定义为
UV＝ { | U & V }
V自身的 n次积记为
Vn=VV…V
规定 V0={ },令
V*=V0∪ V1∪ V2∪ V3∪ …
称 V*是 V的 闭包 ;
记 V＋ ＝ VV*,称 V+是 V的正规闭包 。
上下文无关文法 （ Context-free
grammer,CFG)是这样一种文法，它所定义的语法范畴（或语法单位）是完全独立于这种范畴可能出现的环境的。
2.1.1 上下文无关文法
2.1.1 上下文无关文法
文法,描述语言的语法结构的形式规则
He gave me a book.
<句子 >? <主语 ><谓语 ><间接宾语 ><直接宾语 >
<主语 >? <代词 >
<谓语 >? <动词 >
<间接宾语 >? <代词 >
<直接宾语 >? <冠词 > <名词 >
<代词 >? He|me
<名词 >? book
<冠词 >? a
<动词 >? gave
<句子 > <主语 ><谓语 ><间接宾语 ><直接宾语 >
<代词 ><谓语 ><间接宾语 ><直接宾语 >
He <谓语 ><间接宾语 ><直接宾语 >
He <动词 ><间接宾语 ><直接宾语 >
He gave <间接宾语 ><直接宾语 >
He gave <代词 ><直接宾语 >
He gave me <直接宾语 >
He gave me <冠词 ><名词 >
He gave me a <名词 >
He gave me a book
定义：
一个上下文无关文法 G是一个四元式（ VT,VN,S,P），其中
VT是一个非空有限集，它的每个元素称为 终结符号 ；
VN是一个非空有限集，它的每个元素称为 非终结符号,
VT∩V N＝?；
S是一个非 终结符号，称为 开始符号 ；
P是一个有限的产生式集合，每个产生式的形式是 A→?，
其中,A∈V N,? ∈ （ VT∪V N） *；
开始符号 S至少必须在某个产生式的左部出现一次。
上下文无关文法上下文无关文法的产生式例,c语言的 if-else语句的格式为,
if(expression) statement else statement
用 expr表示 expression,stmt表示 statement
则这个语句的构成规则可以表示为,
Stmt->if (expr) stmt else stmt
“->”读作,定义为,;这样的规则称为 产生式,
直接推出与推导定义：
① 直接推出,
已知串?A?,当 A→?是一个产生式，且?,?∈ （ VT∪ VN） *。
称?A?直接推出，即?A
② 推导,
如果?12?...n，则称这个序列是从?1至?n的一个推导。
推导的每一步实际上是对串中的一个非终结符选择一个以其为左部的产生式的某个候选式进行替换。
推导
+?
1n表示：从?1出发，经一步或若干步，可推导出?
n。
*?
1n表示：从?1出发，经 0步或若干步，可推导出?n。
*S?
},|{)( *TV SGL
定义：假定 G是一个文法,S 是它的开始符号。如果,则称 α 是一个 句型 。
仅含终结符号的句型是一个 句子 。
文法 G所产生的句子的全体是一个 语言,将它记为 L(G)。
例：
G1,E→i
E→E+E
E→E*E
E→(E)
(i*i+i)是文法 (1)的一个句子。
E? (E)? (E+E)? (E*E+E)? (i*E+E)
(i*i+E)? (i*i+i)
E,(E),(E*E+E),…,(i*i+i)是句型。
例：文法 G2(A)：
A? c|Ab
G2(A)的语言?
L(G2)={c,cb,cbb,}
以 c开头，后继若干个 b,即：
L(G2)={ cbn | n≥0 }
例：文法 G1(S)：
S? AB
A? aA|a
B? bB|b
G1(S)的语言?
L(G1)={ambn|m,n>0}
例,构造一个文法 G3
使 L(G3)={anbn| n≥1 }。
G3(S)：
S? aSb
S? ab
例：给出产生语言为 {ambn|1≦ n≦ m≦ 2n}
的文法。
G4(S)：
S? aSb | aaSb
S? ab | aab
从一个句型到另一个句型的推导往往不唯一。
E+E=> i+E=> i+i
E+E=> E+i=> i+i
定义：
最左推导,
任何一步都是对?中的最左非终结符进行替换的。
最右推导,
任何一步都是对?中的最右非终结符进行替换的。
递归
已知文法 G:
E?（ E） | a，求文法 G生成的语言 L(G)
L(G)={（ na） n | n≥0,n是整数 }
此例中在候选式中又出现了产生式左边的结构名，称存在递归。
上例文法若改为 E?（ E），求文法 G生成的语言 L(G)。
L(G)=｛｝！
递归地定义一个结构的文法规则总是必须有至少一个非递归情况（基础情况）。
左递归、右递归
已知文法 G:
E?E a| a，求文法 G生成的语言 L(G)
L(G)={an | n≥0,n是整数 }
此例中在某个候选式的最左边又出现了产生式左边的结构名，称存在 左递归 。
已知文法 G:
E?a E | a，求文法 G生成的语言 L(G)
L(G)={an | n≥0,n是整数 }
此例中在某个候选式的最右边又出现了产生式左边的结构名，称存在 右递归 。
左递归、右递归的通式
一般地，左递归通式如下：
A?A α | β
L(G)={βαn | n≥0,n是整数 }，与正则表达式
βα*相同。
一般地，右递归通式如下：
A?α A | β
L(G)={αnβ| n≥0,n是整数 }，与正则表达式
α*β相同。
利用递归生成重复
若要生成 a*，则需要有生成 ε的规则：
A?ε
再加上用递归来表示重复的候选式：
A?aA或 A?Aa，可得文法为：
A?aA| ε或
A?Aa| ε
2.1.2 语法树与二义性用一张图表示一个句型的推导,称为语法树。
是一个带有以下属性的作了标记的树：
1) 每个节点都用终结符、非终结符或?标出。
2) 根节点用开始符号 S标出。
3) 每个叶节点都用终结符或?标出。
4) 每个非叶节点都用非终结符标出。
5) 如带有标记 A ∈ N 的节点有 n 个带有标记 X1,
X2,.,,Xn 的孩子（可以是终结符也可以是非终结符），就有 A→X 1,X2,.,,Xn ∈ P （文法的一个产生式）。
2.1.2 语法树与二义性
(i*i+i)的语法树
E? (E)
(E+E)
(E*E+E)
(i*E+E)
(i*i+E)
(i*i+i)
E? (E)
(E+E)
(E+i)
(E*E+i)
(E*i+i)
(i*i+i)
一棵语法树是不同推导过程的共性抽象。
如果使用最左 (右 )推导，则一个最左 (右 )
推导与语法树一一对应。
一个句型是否只对应唯一一棵语法树？
E
i
+
*
( )E
i
i
EE
E E
E
+
*
( )
E
i
EE
i i
E E
定义,如果一个文法存在某个句子对应两颗不同的语法树,则说这个 文法是二义的 。
G(E),E? i|E+E|E*E|(E) 是二义文法。
语言的二义性：一个 语言是二义性的,如果对它不存在无二义性的文法。
可能存在 G和 G’，一个为二义的，一个为无二义的。但 L(G)=L(G’)
二义性问题是不可判定问题，即不存在一个算法，它能在有限步骤内，确切地判定一个文法是否是二义的。
可以找到一组无二义文法的充分条件。
二义文法：
G(E),E? i|E+E|E*E|(E)
表达式? 项 |表达式 +项项? 因子 | 项 *因子因子? (表达式 ) | i
无二义文法：
G(E),E? T | E+T
T? F | T*F
F? (E) | i
)
E
F
E
F
F
T
T
T
T
i
+
*
( E
F
i
i
E? T
F
(E)
(E+T)
(T+T)
(T*F+T)
(F*F+T)
(i*F+T)
(i*i+T)
(i*i+F)
(i*i+i)
考虑句子 (i*i+i)
描述程序设计语言时，对于上下文无关文法的限制,
1 不含 P?P形式的产生式
2 每个非终结符 P必须有用处即：
PS
*
**
TVrrP
扩展的表示法,EBNF和语法图
1 EBNF表示法重复和可选的结构在程序设计语言中极为普通，因此在 BNF文法规则基础上扩展包括了用于这两个情况的特殊表示法，这些扩展称作扩展的 BNF（ extended BNF）或 EBNF表示法。
1 EBNF表示法重复情况,重复在文法规则中通过递归表达，常使用左递归或右递归形式，一般规则形式如下：
A → Aa|b （左递归）
A → aA |b （右递归）
EBNF选择使用花括号 {被重复的串 }来表示，上述规则记做：
A→b{a}
A→{a}b
重复的 EBNF表示法举例 1
例：语句序列在右递归格式中写出如下文法：
stmt-sequence → stmt ; stmt -
sequence | stmt
stmt → s
在 EBNF中，它可写为：
stmt-sequence → { stmt ; } stmt
重复的 EBNF表示法举例 2
例：简单表达式文法中的文法规则：
exp → exp addop term | term
这个规则在 EBNF中写作：
exp → term { addop term }
可选情况的 EBNF表示可选情况,EBNF中的可选结构可通过前后用方括号
[.,,]表示出来。
例：带有可选的 else部分的 if语句的文法规则为：
statement → if -stmt | other
if-stmt → if ( exp ) statement|
if (exp) statement else statement
exp → 0 | 1
语句的文法规则在 EBNF中写作：
statement → if -stmt | other
if-stmt → if ( exp ) statement [ else
statement ]
exp → 0 | 1
语法图表示 EBNF规则的图形表示法称作 语法图 。
语法图中使用圆或椭圆表示终结符，方框或矩形框表示非终结符，带箭头的线表示序列和选择。
例：文法规则 factor → ( exp ) | number
用语法图表示则是,
例：考虑简单算术表达式的 BNF。
exp → exp addop term | term
addop → + | -
term → term mulop factor | factor
mulop → *
factor → ( exp ) | number
相对应的 EBNF是
exp → term { addop term }
addop → + | -
term → factor { mulop factor }
mulop → *
factor → ( exp ) | number
举例：简单算术表达式举例：简单算术表达式相对应的语法图,exp → term { addop term }
*
addop → + | - mulop → *
2.1.3 形式语言鸟瞰
Chomsky于 1956年建立形式语言体系，
他把文法分成四种类型,0,1,2,3型。
与上下文无关文法一样，它们都由四部分组成，但对产生式的限制有所不同。
乔姆斯基层次和对应的语法约束文法 G是一个四元式（ VT,VN,S,P）,VT∩V N＝?；
1、若 P中任一产生式都有一般的形式：
→∈ (VT∪V N)+? ∈(V T∪V N)*
且对?,?不加任何其它的限制，则称 G为 0型文法（短语文法） 。
2、若一个 0型文法 G基础上加以限制
｜?｜ ≤ ｜?｜，除 S?ε 外则称 G为 1型文法（上下文有关文法） 。
对非终结符进行替换时要考虑上下文环境。
乔姆斯基层次和对应的语法约束
3、若一个 1型文法 G中所有产生式具有如下的形式
A→? 其中 A∈V N,? ∈ (VT∪V N)+,
则称 G为 2型文法 (上下文无关文法 )。
无论在何处出现 A,它都可被?代替。
4、若在一个 2型文法 G中仅含有形如
A→aB 或 A→a 的产生式，其中 A,B∈V N,a∈V T，
则称 G为右线性文法。类似地，如果 G中仅含有形如
A→Ba 或 A→a 的产生式，则称 G为左线性文法。
通常，把左线性文法及右线性文法统称为 3型文法（正则文法） 。
例：正则表达式：
digit = 0|1|2|3|4|5|6|7|8|9
number = digit digit*
–可改写成文法：
digit → 0|1|2|3|4|5|6|7|8|9
number → number digit | digit
正规文法可以用来表示任何正则表达式能够表示的内容，从而可以设计分析程序，直接从输入源文件中接收字符并与扫描程序一起分配。
0型文法与图灵 (Turing)机等价。
3型文法与有穷自动机等价。
2型文法与下推自动机等价。
四种类型描述能力比较
0型
1型
2型
3型
L5={anbn|n≥1} 不能由正规文法产生，但可由上下文无关文法产生：
G5(S)：
S? aSb| ab
L6={anbncn|n ≥ 1}不能由上下文无关文法产生,但 可由上下文有关文法产生：
G6(S),S? aSBC| aBC
CB? BC
aB? ab
bB? bb
bC? bc
cC? cc
程序设计语言不是上下文无关语言，甚至不是上下文有关语言 。
L7={αcα| α∈ (a|b)*}不能由上下文无关文法产生，甚至连上下文有关文法也不能产生，只能由 0型文法产生。
现今程序设计语言的语言结构，用上下文无关文法描述就足够了。
Language Description and
Implementation
语言描述与实现程序语言的定义
程序语言由两方面定义：
语法
语义
语用教学要点
上下文无关文法
直接推出与推导、最左推导与最右推导
句型、句子与语言
递归与语言
语法树与二义性
EBNF与语法图
乔姆斯基文法一,语法
程序本质上是一定字符集上的 字符串 。
语法,一组规则,用它可以形成和产生一个合式 (well-formed)的程序 。
语 法
词法规则,单词符号的形成规则 。
单词符号是语言中具有独立意义的最基本结构 。 一般包括：常数、标识符、基本字、算符、界符等。
描述工具：有限自动机
语法规则,语法单位的形成规则 。
语法单位通常包括：表达式、语句、分程序、过程、函数、程序等 ;
描述工具：上下文无关文法
G1,E→i
E→E+E
E→E*E
E→(E)
语法规则和词法规则定义了程序的的形式结构。定义语法单位的意义属于语义问题。
二,语义
语义,一组规则,用它可以定义一个程序的意义 。
描述方法：
自然语言描述：隐藏错误、二义性和不完整性
形式描述：
操作语义
指称语义
代数语义
2.1 程序语言的语法描述
几个概念,
考虑一个 有穷 字母表 ∑ 字符集
其中每一个元素称为一个 字符
∑ 上的 字 (也叫 字符串 ) 是指由 ∑ 中的字符所构成的一个有穷序列
不包含任何字符的序列称为 空字,记为 ε
用 ∑ *表示 ∑ 上的所有字的全体,包含空字 ε
例如,设 ∑ ={a,b}，则
∑ *={ε,a,b,aa,ab,ba,bb,aaa,...}
∑*的子集 U和 V的 连接 （ 积 ） 定义为
UV＝ { | U & V }
V自身的 n次积记为
Vn=VV…V
规定 V0={ },令
V*=V0∪ V1∪ V2∪ V3∪ …
称 V*是 V的 闭包 ;
记 V＋ ＝ VV*,称 V+是 V的正规闭包 。
上下文无关文法 （ Context-free
grammer,CFG)是这样一种文法，它所定义的语法范畴（或语法单位）是完全独立于这种范畴可能出现的环境的。
2.1.1 上下文无关文法
2.1.1 上下文无关文法
文法,描述语言的语法结构的形式规则
He gave me a book.
<句子 >? <主语 ><谓语 ><间接宾语 ><直接宾语 >
<主语 >? <代词 >
<谓语 >? <动词 >
<间接宾语 >? <代词 >
<直接宾语 >? <冠词 > <名词 >
<代词 >? He|me
<名词 >? book
<冠词 >? a
<动词 >? gave
<句子 > <主语 ><谓语 ><间接宾语 ><直接宾语 >
<代词 ><谓语 ><间接宾语 ><直接宾语 >
He <谓语 ><间接宾语 ><直接宾语 >
He <动词 ><间接宾语 ><直接宾语 >
He gave <间接宾语 ><直接宾语 >
He gave <代词 ><直接宾语 >
He gave me <直接宾语 >
He gave me <冠词 ><名词 >
He gave me a <名词 >
He gave me a book
定义：
一个上下文无关文法 G是一个四元式（ VT,VN,S,P），其中
VT是一个非空有限集，它的每个元素称为 终结符号 ；
VN是一个非空有限集，它的每个元素称为 非终结符号,
VT∩V N＝?；
S是一个非 终结符号，称为 开始符号 ；
P是一个有限的产生式集合，每个产生式的形式是 A→?，
其中,A∈V N,? ∈ （ VT∪V N） *；
开始符号 S至少必须在某个产生式的左部出现一次。
上下文无关文法上下文无关文法的产生式例,c语言的 if-else语句的格式为,
if(expression) statement else statement
用 expr表示 expression,stmt表示 statement
则这个语句的构成规则可以表示为,
Stmt->if (expr) stmt else stmt
“->”读作,定义为,;这样的规则称为 产生式,
直接推出与推导定义：
① 直接推出,
已知串?A?,当 A→?是一个产生式，且?,?∈ （ VT∪ VN） *。
称?A?直接推出，即?A
② 推导,
如果?12?...n，则称这个序列是从?1至?n的一个推导。
推导的每一步实际上是对串中的一个非终结符选择一个以其为左部的产生式的某个候选式进行替换。
推导
+?
1n表示：从?1出发，经一步或若干步，可推导出?
n。
*?
1n表示：从?1出发，经 0步或若干步，可推导出?n。
*S?
},|{)( *TV SGL
定义：假定 G是一个文法,S 是它的开始符号。如果,则称 α 是一个 句型 。
仅含终结符号的句型是一个 句子 。
文法 G所产生的句子的全体是一个 语言,将它记为 L(G)。
例：
G1,E→i
E→E+E
E→E*E
E→(E)
(i*i+i)是文法 (1)的一个句子。
E? (E)? (E+E)? (E*E+E)? (i*E+E)
(i*i+E)? (i*i+i)
E,(E),(E*E+E),…,(i*i+i)是句型。
例：文法 G2(A)：
A? c|Ab
G2(A)的语言?
L(G2)={c,cb,cbb,}
以 c开头，后继若干个 b,即：
L(G2)={ cbn | n≥0 }
例：文法 G1(S)：
S? AB
A? aA|a
B? bB|b
G1(S)的语言?
L(G1)={ambn|m,n>0}
例,构造一个文法 G3
使 L(G3)={anbn| n≥1 }。
G3(S)：
S? aSb
S? ab
例：给出产生语言为 {ambn|1≦ n≦ m≦ 2n}
的文法。
G4(S)：
S? aSb | aaSb
S? ab | aab
从一个句型到另一个句型的推导往往不唯一。
E+E=> i+E=> i+i
E+E=> E+i=> i+i
定义：
最左推导,
任何一步都是对?中的最左非终结符进行替换的。
最右推导,
任何一步都是对?中的最右非终结符进行替换的。
递归
已知文法 G:
E?（ E） | a，求文法 G生成的语言 L(G)
L(G)={（ na） n | n≥0,n是整数 }
此例中在候选式中又出现了产生式左边的结构名，称存在递归。
上例文法若改为 E?（ E），求文法 G生成的语言 L(G)。
L(G)=｛｝！
递归地定义一个结构的文法规则总是必须有至少一个非递归情况（基础情况）。
左递归、右递归
已知文法 G:
E?E a| a，求文法 G生成的语言 L(G)
L(G)={an | n≥0,n是整数 }
此例中在某个候选式的最左边又出现了产生式左边的结构名，称存在 左递归 。
已知文法 G:
E?a E | a，求文法 G生成的语言 L(G)
L(G)={an | n≥0,n是整数 }
此例中在某个候选式的最右边又出现了产生式左边的结构名，称存在 右递归 。
左递归、右递归的通式
一般地，左递归通式如下：
A?A α | β
L(G)={βαn | n≥0,n是整数 }，与正则表达式
βα*相同。
一般地，右递归通式如下：
A?α A | β
L(G)={αnβ| n≥0,n是整数 }，与正则表达式
α*β相同。
利用递归生成重复
若要生成 a*，则需要有生成 ε的规则：
A?ε
再加上用递归来表示重复的候选式：
A?aA或 A?Aa，可得文法为：
A?aA| ε或
A?Aa| ε
2.1.2 语法树与二义性用一张图表示一个句型的推导,称为语法树。
是一个带有以下属性的作了标记的树：
1) 每个节点都用终结符、非终结符或?标出。
2) 根节点用开始符号 S标出。
3) 每个叶节点都用终结符或?标出。
4) 每个非叶节点都用非终结符标出。
5) 如带有标记 A ∈ N 的节点有 n 个带有标记 X1,
X2,.,,Xn 的孩子（可以是终结符也可以是非终结符），就有 A→X 1,X2,.,,Xn ∈ P （文法的一个产生式）。
2.1.2 语法树与二义性
(i*i+i)的语法树
E? (E)
(E+E)
(E*E+E)
(i*E+E)
(i*i+E)
(i*i+i)
E? (E)
(E+E)
(E+i)
(E*E+i)
(E*i+i)
(i*i+i)
一棵语法树是不同推导过程的共性抽象。
如果使用最左 (右 )推导，则一个最左 (右 )
推导与语法树一一对应。
一个句型是否只对应唯一一棵语法树？
E
i
+
*
( )E
i
i
EE
E E
E
+
*
( )
E
i
EE
i i
E E
定义,如果一个文法存在某个句子对应两颗不同的语法树,则说这个 文法是二义的 。
G(E),E? i|E+E|E*E|(E) 是二义文法。
语言的二义性：一个 语言是二义性的,如果对它不存在无二义性的文法。
可能存在 G和 G’，一个为二义的，一个为无二义的。但 L(G)=L(G’)
二义性问题是不可判定问题，即不存在一个算法，它能在有限步骤内，确切地判定一个文法是否是二义的。
可以找到一组无二义文法的充分条件。
二义文法：
G(E),E? i|E+E|E*E|(E)
表达式? 项 |表达式 +项项? 因子 | 项 *因子因子? (表达式 ) | i
无二义文法：
G(E),E? T | E+T
T? F | T*F
F? (E) | i
)
E
F
E
F
F
T
T
T
T
i
+
*
( E
F
i
i
E? T
F
(E)
(E+T)
(T+T)
(T*F+T)
(F*F+T)
(i*F+T)
(i*i+T)
(i*i+F)
(i*i+i)
考虑句子 (i*i+i)
描述程序设计语言时，对于上下文无关文法的限制,
1 不含 P?P形式的产生式
2 每个非终结符 P必须有用处即：
PS
*
**
TVrrP
扩展的表示法,EBNF和语法图
1 EBNF表示法重复和可选的结构在程序设计语言中极为普通，因此在 BNF文法规则基础上扩展包括了用于这两个情况的特殊表示法，这些扩展称作扩展的 BNF（ extended BNF）或 EBNF表示法。
1 EBNF表示法重复情况,重复在文法规则中通过递归表达，常使用左递归或右递归形式，一般规则形式如下：
A → Aa|b （左递归）
A → aA |b （右递归）
EBNF选择使用花括号 {被重复的串 }来表示，上述规则记做：
A→b{a}
A→{a}b
重复的 EBNF表示法举例 1
例：语句序列在右递归格式中写出如下文法：
stmt-sequence → stmt ; stmt -
sequence | stmt
stmt → s
在 EBNF中，它可写为：
stmt-sequence → { stmt ; } stmt
重复的 EBNF表示法举例 2
例：简单表达式文法中的文法规则：
exp → exp addop term | term
这个规则在 EBNF中写作：
exp → term { addop term }
可选情况的 EBNF表示可选情况,EBNF中的可选结构可通过前后用方括号
[.,,]表示出来。
例：带有可选的 else部分的 if语句的文法规则为：
statement → if -stmt | other
if-stmt → if ( exp ) statement|
if (exp) statement else statement
exp → 0 | 1
语句的文法规则在 EBNF中写作：
statement → if -stmt | other
if-stmt → if ( exp ) statement [ else
statement ]
exp → 0 | 1
语法图表示 EBNF规则的图形表示法称作 语法图 。
语法图中使用圆或椭圆表示终结符，方框或矩形框表示非终结符，带箭头的线表示序列和选择。
例：文法规则 factor → ( exp ) | number
用语法图表示则是,
例：考虑简单算术表达式的 BNF。
exp → exp addop term | term
addop → + | -
term → term mulop factor | factor
mulop → *
factor → ( exp ) | number
相对应的 EBNF是
exp → term { addop term }
addop → + | -
term → factor { mulop factor }
mulop → *
factor → ( exp ) | number
举例：简单算术表达式举例：简单算术表达式相对应的语法图,exp → term { addop term }
*
addop → + | - mulop → *
2.1.3 形式语言鸟瞰
Chomsky于 1956年建立形式语言体系，
他把文法分成四种类型,0,1,2,3型。
与上下文无关文法一样，它们都由四部分组成，但对产生式的限制有所不同。
乔姆斯基层次和对应的语法约束文法 G是一个四元式（ VT,VN,S,P）,VT∩V N＝?；
1、若 P中任一产生式都有一般的形式：
→∈ (VT∪V N)+? ∈(V T∪V N)*
且对?,?不加任何其它的限制，则称 G为 0型文法（短语文法） 。
2、若一个 0型文法 G基础上加以限制
｜?｜ ≤ ｜?｜，除 S?ε 外则称 G为 1型文法（上下文有关文法） 。
对非终结符进行替换时要考虑上下文环境。
乔姆斯基层次和对应的语法约束
3、若一个 1型文法 G中所有产生式具有如下的形式
A→? 其中 A∈V N,? ∈ (VT∪V N)+,
则称 G为 2型文法 (上下文无关文法 )。
无论在何处出现 A,它都可被?代替。
4、若在一个 2型文法 G中仅含有形如
A→aB 或 A→a 的产生式，其中 A,B∈V N,a∈V T，
则称 G为右线性文法。类似地，如果 G中仅含有形如
A→Ba 或 A→a 的产生式，则称 G为左线性文法。
通常，把左线性文法及右线性文法统称为 3型文法（正则文法） 。
例：正则表达式：
digit = 0|1|2|3|4|5|6|7|8|9
number = digit digit*
–可改写成文法：
digit → 0|1|2|3|4|5|6|7|8|9
number → number digit | digit
正规文法可以用来表示任何正则表达式能够表示的内容，从而可以设计分析程序，直接从输入源文件中接收字符并与扫描程序一起分配。
0型文法与图灵 (Turing)机等价。
3型文法与有穷自动机等价。
2型文法与下推自动机等价。
四种类型描述能力比较
0型
1型
2型
3型
L5={anbn|n≥1} 不能由正规文法产生，但可由上下文无关文法产生：
G5(S)：
S? aSb| ab
L6={anbncn|n ≥ 1}不能由上下文无关文法产生,但 可由上下文有关文法产生：
G6(S),S? aSBC| aBC
CB? BC
aB? ab
bB? bb
bC? bc
cC? cc
程序设计语言不是上下文无关语言，甚至不是上下文有关语言 。
L7={αcα| α∈ (a|b)*}不能由上下文无关文法产生，甚至连上下文有关文法也不能产生，只能由 0型文法产生。
现今程序设计语言的语言结构，用上下文无关文法描述就足够了。
