Microsoft PowerPoint - 2-FormalLang.ppt

Size: px

Start display at page:

Download "Microsoft PowerPoint - 2-FormalLang.ppt"

柯变戴
5 years ago
Views:

1 第二章高级语言及其语法描述 2.1 程序设计语言的定义 2.2 高级语言的一般特性 2.3 程序设计语言的语法描述本章目的 : 简要了解高级语言的主要内容及特点 ; 掌握上下文无关文法及语法树作业 : p35-36:1(1)(2)(5),4, 号交程序设计语言历史 50 s: Fortran & Lsp 60 s: Algol, PL/1, Smula67 70 s: Pascal, Prolog, C, ML, Smalltalk 80 s: Common Lsp, C, Ada 90 s: Fortran90,Ans C, Tcl, Java 00 s: C#, Java2 ^ As of May 2006 The ncyclopeda of Computer Languages by Murdoch Unversty, Australa lsts 8512 computer languages. A.M. Turng Award 2.1 程序设计语言的定义是符号的非空有穷集合程序是字母字母表表上的一个字符串 A,B,,Y,Z,0,1,,9, 空格,,-,,/,=,<,>,(,),[,],,,,\,,.,:,^ 词法单位定义语言文法的一部分 ( 词法规则 ) 常数标识符保留字运算符分界符特殊符号语法单位定义语言文法的另一部分 ( 语法规则表达式语句复合语句程序等 / 产生式规则 ) 语义描述单词符号和语法单位的含义函数副作用类型推理规则各类语句的执行规则等字符串词法语法语义语言定义举例 0.5X1C 常数 0.5; 算符 ; 标识符 X1; 算符 ; 标识符 C 表达式 0.5X1C 如果 X1 为非双精度型变量则先进行类型转换然后乘 ; 如果 C 为非双精度型变量则先进行类型转换然后加 ; 结果转换成单精度型 Ynlang Zhao 1

2 符号串词法语法语义语言定义举例 fact(nt n)f(n<=0)return 1elsereturn nfact(n-1); 标识符 fact; 括号 (; 保留字 nt; 标识符 n; 括号 ); 括号 ; 保留字 f; 函数定义 fact(nt n) 函数定义缺省类型为整型 ; 参数结合规则 ; 函数副作用规则 ; 返回值类型转换规则如何精确定义一个语言? 2.2 高级语言的一般特性数据类型用于描述数据整型实型双精度型字符型布尔型数组结构类初等数据类型 ; 复合数据类型 ; 语句用于描述功能抽象数据类型 / 加工赋值语句循环语句条件语句说明语句调用语句返回语句语言分类语言的范型强制式 Imperatve 应用式 Applcatve 基于规则 Rule-Based 面向对象 Object-Orented 数据类型举例复合数据类型用于描述数据结构抽象数据类型用于描述数据和代码的封装继承多态 record year : ; month : 1..12; day : 初等数据类型用于描述数据 char ch; nt book_no; float amount; record name, frstname : strng; age : 0..99; case marred : Boolean of true : (Spousesname : strng); false : ( ) 程序结构 : Fortran 语言 program man some declaratons real alpha, beta common /coeff/ alpha, beta statements stop subroutne sub1 (some arguments) declaratons of arguments real alpha, beta common /coeff/ alpha, beta statements return subroutne sub2 (some arguments) declaratons of arguments real alpha, beta common /coeff/ alpha, beta statements return PROGRAM MAIN ND SUBROUTIN SUB1 ND SUBROUTIN SUB2 ND 程序结构 : Pascal 语言 program ScopeDemo; var A : nteger; procedure ScopeInner; var A : nteger; A := 10; wrteln (A) ; ( Man ) A := 20; wrteln (A); ScopeInner; wrteln (A);. ( Man ) program man procedure p1; procedure p2; ; ;. Ynlang Zhao 2

720 函数调用基于规则语言 Prolog nrev([],[]). 等 nrev([a X],Y):-nrev(X,Z),app(Z,[A],Y). 规则序列 app([],x,x). 面向对象语言 Smalltalk,C,Java app([t C],Y,[T Z]):-app(C,Y,Z). 等类和实例 :-nrev([1,2,3,4,5],l)).

3 程序结构 : C 语言预处理命令类型说明函数原型声明变量说明函数定义 type fn (parameters) local-vars; statements; vod c_functon1(nt a, float b)... nt c_functon2(nt a, float b) nt r;... return r; nt man(vod) nt a, r; float b; c_functon1(a, &b); r = c_functon2(a, &b); (defun fact(n) 语言分类 (f (<= n 1) 1 强制式语言 Fortran,C,Pascal,Ada 等 ( n (fact (1- n))))) 语句序列应用式语言 LISP,ML >(fact 6) 等 720 函数调用基于规则语言 Prolog nrev([],[]). 等 nrev([a X],Y):-nrev(X,Z),app(Z,[A],Y). 规则序列 app([],x,x). 面向对象语言 Smalltalk,C,Java app([t C],Y,[T Z]):-app(C,Y,Z). 等类和实例 :-nrev([1,2,3,4,5],l)). L = [5,4,3,2,1] Contnue search?(y or N): y no 2.3 程序设计语言的语法描述文法引论上下文无关文法语法分析树文法的二义性问题形式语言简介 =a, b, # =ε, 文法引论 a, b, #, aa, ab, a#, ba, bb, b#, aaa, 基本术语有穷字母表 : 上的符号串 : 符号的有穷集合中的符号的一个有穷序列空符号串 / 空字 ε : 不包含任何符号的符号串 : 符号串集合 U: 上所有符号串的全体 U Σ 基本术语符号串集合的连接 ( 积 ): UV = V 0 αβ α U β V, U Σ, Σ 结合律 :( UV ) W = U( VW ) 无交换律 : UV VU n V = VV... V 自身的 n 次连接的连接 ( 积 ) V = ε V的闭包 V V V V : =... V的正则闭包 : V = VV Ynlang Zhao 3

4 举例 =a, b, # =ε, a, b, #, aa, ab, a#, ba, bb, b#, aaa, U=ε, a, #, aa V=ab, a#, bb UV=ab, a#, bb, aab, aa#, abb, #ab, #a#, #bb, aaab, aaa#, aabb VU= ab, aba, ab#, abaa, a#, a#a, a##, a#aa, bb, bba, bb#, bbaa U 2 =ε, a, #, aa, a#, aaa, #a, ##, #aa, aa#, aaaa 自然语言语法分析的例子语法分析 :He gave me a book. < 句子 >->< 主语 > < 谓语 > < 间接宾语 > < 直接宾语 > < 主语 >->< 代词 > < 谓语 >->< 动词 > < 间接宾语 >->< 代词 > 非终结符 < 直接宾语 >->< 冠词 > < 代词 > < 代词 >->He < 代词 >->me < 冠词 >->a < 动词 >->gave < 名词 >->book 左部终结符产生式的右部用于对该句进行语法分析的产生式规则推导 :He gave me a book. 开始符号 S < 句子 > 非终结符号 V N < 句子 >=>< 主语 > < 谓语 > < 间接宾语 > < 直接宾语 > =>< 代词 > < 谓语 > < 间接宾语 > < 直接宾语 > =>He < 谓语 > < 间接宾语 > < 直接宾语 > =>He < 动词 > < 间接宾语 > < 直接宾语 > =>He gave < 间接宾语 > < 直接宾语 > =>He gave < 代词 > < 直接宾语 > =>He gave me < 直接宾语 > =>He gave me < 冠词 > < 名词 > =>He gave me a < 名词 > =>He gave me a book < 主语 > < 谓语 > < 间接宾语 > < 直接宾语 > < 代词 > < 动词 > < 代词 > < 冠词 > < 名词 > He gave me a book 终结符号 V T 上下文无关文法一个文法 G 是一个四元组 : G=(V T,V N,S, P ) 终结符集合 V T 是终结符号的非空有限集终结符号是组成语言的基本符号, 不可再分解非终结符集合 V N 是非终结符号的非空有限集非终结符号用来代表语法范畴开始符号 S 开始符号是一个特殊的非终结符号, 代表语言中最感兴趣的语法范畴产生式集合 P 产生式规则是定义语法范畴的一种书写规则上下文无关文法文法 G=(V T,V N,S, P ) V T V N =φ 若 (P,α) P, 则 P V N α (V T V N ) 开始符号 S 至少必须在某个产生式的左部出现一次 Ynlang Zhao 4

5 产生式规则的书写形式 1 大写拉丁字母表示非终结符 2 小写拉丁字母表示终结符 3 小写希腊字母表示由终结符和非终结符构成的符号串 A α 左部为一个非终结符右部是符号串, 由终结符和非终结符组成 -> -> -> ->() 产生式规则 P α1 P α M 2 P α -> -> -> ->() n 每个 α 称为 P 的候选式,=1..n P α1 α2 L αn -> () 推导与直接推导推导与直接推导对于 ( A, γ ) P 且 αβ, (V V ), 字符串 αaβ使用一次规则 A γ得到 αγβ, 称 αaβ 直接推导出 αγβ, 记为 αaβ αγβ 例 : -> () =>() 是直接推导, 其中 α=β=ε => 不是直接推导 => 是直接推导, 其中 α=ε, β= N T 对于 α, α, L, α (V V ), 1 2 n N T 如果 α α L α 1 2 n 则称其为从 α 到 α 的一个推导. 1 n 例 : -> () =>() 是推导 =>=> 是推导 => 是推导推导与直接推导例 : -> () =>=>=>()=>()=> ()=>()=>()=>() =>=>=>=>=>()=>( )=>()=>() 对于推导 α α L α, 若其中的直接推导 1 2 n α1 αn, 否则记为 α1 αn 步数不少于 1, 则记为句子句型和语言文法 G 1 S->bA A->aA a 假定文法 G的开始符号为 S, 如果 S α则称 α是一个句型仅含终结符号的句型称为句子 L(G 1 )=ba n n>=1 句子的全体是一个语言, 记为 L(G) 文法 G 2 S->AB A->aA a B->bB b L(G 2 )=a m b n m,n>=1 T L(G)= α S α α V Ynlang Zhao 5

6 最左推导与最右推导语法分析树与二义性最左 ( 右 ) 推导是一种推导, 其中每一步直接推导中都是对最左 ( 右 ) 边的非终结符号使用产生式规则进行替换得到例 : -> () 2 3 最左推导最右推导 =>=>=>=>=>()=>( )=>()=>() =>=>=>()=>()=> ()=>()=>()=>() > () () ( ) 1 语法分析树与二义性句型的语法分析树 ( ) 5 6 一颗语法树表示了一个句型的部分或全部不同推导过程, 包括最左最右推导. 句型的语法分析树 =>=>=> =>=> =>=>=> =>=> 二义性文法如果一个文法存在某个句子对应两颗不同的语法树, 则称这个文法是二义的. 若一个文法中存在某个句子, 它有两个不同的最左 ( 最右 ) 推导, 则这个文法是二义的. =>=>=> =>=> =>=>=> =>=> 文法的二义性是不可判定的. 为文法二义性判定寻找充分条件. Ynlang Zhao 6

7 文法 G2 是在文法 G1 的基础上加了如下归约限定 : 1 连从左到右 2 连从左到右 3 先后 1 对于先归约对于先归约对于先归约对于先归约 2 3 文法 G1: -> () 文法 G2: ->T T T->F TF F->() 结论 : L(G1)=L(G2) 无二义性文法的任意句子的语法树是唯一的, 所以该句子的最左推导唯一总结 : 以后均讨论无二义性文法, 同时有下面的约定 : 文法中不含形如 P->P T 的产生式规则 ; T 每个非终结符必须都有用处 T, 即对于任一非终结符 P, 有 F T T F T F S αp β (P γ, γ V TF ) F F 形式语言简介 0 型文法 ( αβ, ) P 有 : 1 型文法 2 型文法 3 型文法 Chomsky 文法 G = ( V, V, S, P ) α β, α ( V V ) ( V ), β ( V V ) N T T N T G 的任何产生式 α β 均满足 α <= β, 仅 S ε 除外, 且 β 中不含 S; A β, A VN, β ( VN VT) A αb, 或, A α, 且 A, B V, α ( V ) N t N T 本章小结字母表符号串终结符号, 非终结符号, 开始符号, 产生式直接推导推导句型句子语言语法树规约二义性文法 Chomsky 文法 Ynlang Zhao 7

Microsoft PowerPoint - 2-FormalLang12.ppt [兼容模式]

Microsoft PowerPoint - 2-FormalLang12.ppt [兼容模式] Compler2012LanguageFeatures Ynlang Zhao ( 赵银亮 ) X an Jaotong Unversty Chapter 2 Overvew of Hgh-Level Programmng Languages 第二章高级语言及其语法描述程序设计语言的定义高级语言的一般特性程序设计语言的语法描述 Ynlang Zhao X an Jaotong Unversty 2012