编译原理 形式语言

编译原理形式语言编译原理是计算机科学与技术领域中的一门重要课程，它研究的是将高级语言程序转换为计算机可以理解和执行的可执行代码的过程。

在学习编译原理的过程中，我们必然要涉及到形式语言的概念。

形式语言是指用来描述计算机语言、编程语言、自然语言或者其他领域中的形式系统的语言。

形式语言可以分为四种类型：无限制文法、上下文有关文法、上下文无关文法和正则文法。

这四种类型的文法按照规则严格程度从高到低依次排列，其中无限制文法最为灵活，正则文法最为严格，限制最多。

无限制文法（Unrestricted Grammar）是最灵活最强大的文法类型，也是图灵机的模型之一、它的产生式规则形式可以是 A -> α，其中 A是一个非终结符号（可以通过其他规则推导出其他符号或者字符串），α 是一个终结符符号或非终结符符号的有限序列。

无限制文法没有任何限制，可以描述任意的形式语言。

上下文有关文法（Context-Sensitive Grammar）是介于无限制文法和上下文无关文法之间的一种文法类型。

它的产生式规则形式可以是αAβ -> αγβ，其中α、β、γ 是终结符号或非终结符号的有限序列，A 是一个非终结符号。

上下文有关文法要求产生式规则中的左右上下文必须匹配。

上下文有关文法可以描述一些复杂的结构，但与无限制文法相比，它的限制更多一些。

上下文无关文法（Context-Free Grammar）是应用最广泛的一种文法类型，它的产生式规则形式可以是 A -> α，其中 A 是一个非终结符号，α 是一个终结符号或非终结符号的有限序列。

上下文无关文法的产生式规则没有左右上下文的限制，只要符合规则形式即可。

上下文无关文法广泛应用于编译器的语法分析阶段，例如语法分析器常采用的 LL(1) 文法和 LR(1) 文法。

正则文法（Regular Grammar）是最严格、最受限制的一种文法类型，它的产生式规则形式可以是 A -> aB 或 A -> a，其中 A 和 B 是非终结符号，a 是终结符号。

第2章形式语言基础2.2 设有文法G[N]: N -> D | NDD -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9(1)G[N]定义的语言是什么?(2)给出句子0123和268的最左推导和最右推导。

解答：(1)L(G[N])={(0|1|2|3|4|5|6|7|8|9)+} 或L(G[N])={α| α为可带前导0的正整数}(2)0123的最左推导：N ⇒ ND ⇒ NDD ⇒ NDDD ⇒ DDDD ⇒ 0DDD ⇒ 01DD ⇒ 012D ⇒ 0123 0123的最右推导：N ⇒ ND ⇒ N3 ⇒ ND3 ⇒ N23 ⇒ ND23 ⇒ N123 ⇒ D123 ⇒ 0123268的最左推导：N ⇒ ND ⇒ NDD ⇒ DDD ⇒ 2DDD ⇒ 26D ⇒ 268268的最右推导：N ⇒ ND ⇒ N8 ⇒ ND8 ⇒ N68 ⇒ D68 ⇒ 2682.4 写一个文法，使其语言是奇数的集合，且每个奇数不以0开头。

解答：首先分析题意，本题是希望构造一个文法，由它产生的句子是奇数，并且不以0开头，也就是说它的每个句子都是以1、3、5、7、9中的某个数结尾。

如果数字只有一位，则1、3、5、7、9就满足要求，如果有多位，则要求第1位不能是0，而中间有多少位，每位是什么数字（必须是数字）则没什么要求，因此，我们可以把这个文法分3部分来完成。

分别用3个非终结符来产生句子的第1位、中间部分和最后一位。

引入几个非终结符，其中，一个用作产生句子的开头，可以是1－9之间的数，不包括0，一个用来产生句子的结尾，为奇数，另一个则用来产生以非0整数开头后面跟任意多个数字的数字串，进行分解之后，这个文法就很好写了。

N -> 1 | 3 | 5 | 7 | 9 | BNB -> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | B02.7 下面文法生成的语言是什么？G1：S->ABA->aA| εB->bc|bBc G2：S->aA|a A->aS解答：B ⇒ bcB ⇒ bBc⇒ bbccB ⇒ bBc⇒ bbBcc ⇒ bbbccc……A ⇒εA ⇒ aA ⇒ aA ⇒ aA ⇒ aaA ⇒ aa……∴S ⇒ AB ⇒ a m b n c n , 其中m≥0,n≥1即L(G1)={ a m b n c n | m≥0,n≥1} S ⇒ aS ⇒ aA ⇒ aaS ⇒ aaaS ⇒ aA ⇒ aaS ⇒ aaaA ⇒aaaaS ⇒ aaaaa ……∴S ⇒ a2n+1 , 其中n≥0即L(G2)={ a2n+1 | n≥0}2.11 已知文法G[S]: S->(AS)|(b)A->(SaA)|(a)请找出符号串(a)和(A((SaA)(b)))的短语、简单短语和句柄。

第2章形式语言1．试分别构造产生下列语言的文法：（1）{a n#b n|n≥0}∪{c n#d n|n≥0}；（2）任何不是以0打头的所有奇整数所组成的集合。

答：(1) 对应文法为G(S)=({S,X,Y},{a,b,c,d,#}, {S→X, S→Y, X→aXb|#, Y→cYd|# },S)(2) G(S)=({S,A,B,I,J},{0,1,2,3,4,5,6,7,8,9},{S→J|IBJ, B→0B|IB|ε, I→J|2|4|6|8, J→1|3|5|7|9},S)2．对于下列的文法S→AB|c A→bA|a B→aSb|c试给出句子bbaacb的最右推导。

答：S=>AB=>AaSb=> Aacb=>bAacb=>bbAacb=>bbaacb3．已知文法G[S]: S->(AS)|(b)A->(SaA)|(a)请找出符号串(a)和(A((SaA)(b)))的短语、简单短语和句柄。

答：因为S 不能⇒ (a), 所以(a)不是文法的句型。

没有短语、直接短语和句柄。

因为S ⇒(AS) ⇒(A(AS)) ⇒(A((SaA)S)) ⇒(A((SaA)(b))),所以(A((SaA)(b)))是文法的句型。

短语：(A((SaA)(b)))，((SaA)(b))，(SaA)，(b)直接短语：(SaA)，(b)句柄：(SaA)S( A S )( A S )( S a A ) ( b )4．试描述由下列文法所产生的语言的特点：（1）S→10S0 S→aA A→bA A→a（2）S→aSS S→a答：(1) 本文法构成的语言集为：L(G)={(10)n ab m a0n|n,m≥0}。

(2)由L(G)={a2n-1|n≥1}可知，该语言特点是：产生的句子是奇数个a。

附加题：试证明文法S→AB|DC A→aA|a B→bBc|bc C→cC|c D→aDb|ab为二义性文法。