第2章_形式语言的基本知识.ppt

程序设计语言 如何描述或定义 如何识别和分析 形式语言： 用一组数学符号和规则来描述的语言称为形式语言 形式语言理论是对符号串集合的表示法、结构及其特性的研究，是程序设计语言语法分析研究的基础。 文法习惯上只将产生式写出，并可有如下约定： 第一条产生式的左部是开始符号 用尖括号括起的是非终结符，否则为终结符，或者大写字母表示非终结符，小写字母或其他字符表示终结符。 G可写成G[S]，S是开始符号 [例] G： S →0S1 S →01 一棵语法树表示了一个句型的种种可能的(但未必是所有的)不同推导过程，包括最左(最右)推导。 但是，一个句型是否只对应唯一的一棵语法树呢?一个句型是否只有唯一的一个最左(最右)推导呢? S→aSBE S→aBE BE→bE aB→ab bB→bb bE→be eE→ee 例：2型（上下文无关）文法 文法G[S]： S→AB A→BS|0 B→SA|1 　　　　　　 S→ε 上下文无关文法有足够的能力描述现今程序设计语言的语法结构，比如描述算术表达式，描述各种语句等等。 因此我们关心上下文无关文法形成的语言的句子的分析和分析方法的研究。今后，对文法一词若无特别说明，则均指上下文无关文法。 G[S]： S→0A|1B|0 A→0A|1B|0S B→1B|1|0 标识符（字母开始的字母数字串）的有效长度是10 数字最多为14位 过程无参，可嵌套（最多三层）定义，可递归调用 变量的作用域同PASCAL 13个保留字：if, then, while, do, read, write, call, begin, end, const, var, procedure, odd 练习 3. 写一文法，使其语言是偶正整数的集合。 要求： 允许0打头 (2)?不允许0打头 ?4.证明下述文法G［〈表达式〉］是二义的。 〈表达式〉∷=a|(〈表达式〉)|〈表达式〉〈运算符〉〈表达式〉 〈运算符〉∷=+|-|*|/ ? 5. 令文法G［E］为： E→T|E+T|E-T T→F|T*F|T/F F→(E)|i 证明E+T*F是它的一个句型 练习 6. 给出生成下述语言的上下文无关文法： （1）{ anbnambm| n，m=0} (2) { 1n0m 1m0n| n，m=0} 7. 给出生成下述语言的三型文法： (1) { anbm|n,m=1 } (2){anbmck|n,m,k=0 } ? 8 给出下述文法所对应的正规式： S→0A|1B A→1S|1 B→0S|0 2.4　文法和语言的分类 形式语言(乔姆斯基)：通过抽象，对语言进行形式化描述 用一组数学符号和规则来描述的语言称为形式语言 　　?*的任何子集称作?上的形式语言 L（G[S]）={α | α ∈VT*,S ? α } + 由文法定义语言 文法和语言分类：0型、1型、2型、3型 这几类文法的差别在于对产生式施加不同的限制。 0型语言：L0 0型文法称为无约束短语结构文法。规则的左部和右部都可以是符号串，一个短语可以产生另一个短语。 0型： P： α ::=β 其中α∈V*且至少含有一个非终结符，β∈V* 0型文法 G[S]: S→ABS|AB AB→BA A→0 B→1 L(G[S])={x|x是由n个01或10组成的二进制数字串，n≥1} 该文法产生的语言为 S→ACaB Ca→aaC CB→DB aB→Ba CB→E aD→Da AD→AC aE→Ea AE→ε 例：0型 文法G[S]： L0={ai|i是2的正整次方} L0={aa,aaaa,aaaaaaaa,……} 1型文法 ： P： αAβ ::= αγβ 其中 A∈VN，α，β ∈V*， γ ∈V＋ 1型语言：L1 称为上下文敏感或上下文有关。也即只有在α 、 β这样的 上下文中才能把A改写为γ 例：1型（上下文有关）文法G[S]： L(G)={anbnen|n ≥ 1 } 2型： P： A::= β 其中 A∈ VN ， β ∈V* 2型语言：L2 称为上下文无关文法。也即把A改写为β时，不必考虑上下文。 （右线性） P： A:=a 或