形式语言的基本知识.ppt

北京林业大学信息学院 2020年 10月 16日 第 2章 形式语言的基本知识 1. 本章是 编译原理课程的理论基础 ，要求掌握形 式语言的基本术语和概念。 2. 掌握文法和语言的定义，文法的二义性与递归 性的判断方法及句型的分析方法。 3. 熟练使用文法定义程序设计语言的单词和语法 成分。 4. 对形式语言的理论有一个初步认识。 教学目标 北京林业大学信息学院 2020年 10月 16日 2.1 字母表和符号串的基本概念 2.2 文法和语言的形式定义 2.3 句型的分析 2.4 文法和语言的分类 2.5 PL/0编译程序概述 教学内容 北京林业大学信息学院 2020年 10月 16日 字母表 ：符号的非空有限集 例： =0， 1 2.1 字母表和符号串 符号 ：字母表中的元素 例： 0， 1 符号串 ：由字母表中的符号组成的任何有穷序列 例： 0,1, 01, 10, 011， . 空符号串 ：无任何符号的符号串，用 表示 C语言的字母表 A a,b,0,1,9, +, , ,_/, ( , ), = if, else,for. 不对 如 =if,else,for,while 符号就是字符，对吗？ 北京林业大学信息学院 2020年 10月 16日 符号串的前缀和后缀 : 从符号串 s的尾部删去若干个 (包括 0个 )符号之后所余下的 部分称为 s的前缀 ， 0， 01及 011都是符号串 011的前缀 ， 1， 11及 011都是符号串 011的后缀 符号串集合 ：若集合 A中的一切元素都是某字母表上的符号 串，则称 A为该字母表上的符号串集合。 例： =a， b， c A= a,aa,ac 北京林业大学信息学院 2020年 10月 16日 符号串的运算 符号串 x和 y的 连接 :是把 y的符号写在 x的符号之后 得到的符号串 xy 例如 x=00， y=11，则 xy=0011 对于任意一个符号串 s，有 s= s=s 符号串的连接运算 北京林业大学信息学院 2020年 10月 16日 符号串自身连接 n次得到的符号串 sn 定义为 ss ss ，包括 n个 s，称为符号串的 幂运算 s0= ， s1=s， s2=ss， 设 s=01，则 s0= s1=01 s2=0101 符号串的幂运算 北京林业大学信息学院 2020年 10月 16日 设 A、 B为符号串集合，则 A和 B的 乘积 定义为： AB xy |xA,yB 例如， A a,b， B=c,d 则 AB= 符号串集合的乘积 ac,ad,bc,bd 北京林业大学信息学院 2020年 10月 16日 有符号串集合 A，定义 A0 =, A1=A, A2=AA, A3=AAA, A n An-1A=AAn-1 ， n0 例如， A 0,1，则 A0= A1= A2= A3= 符号串集合的幂运算 0,1 00,01,10,11 000,001,010,011,100,101,110,111 北京林业大学信息学院 2020年 10月 16日 设 A是符号串集合，定义 A A1 A2 A3 An 称为集合 A的 正闭包 。 A* A0 A 称为集合 A的 闭包 。 例： A=x,y A ？ A* ？ x,y, xx,xy,yx,yy , xxx,xxy,xyx,xyy, A1 A2 A3 , x,y, xx,xy,yx,yy , xxx,xxy,xyx,xyy, A0 A1 A2 A3 符号串集合的闭包运算 北京林业大学信息学院 2020年 10月 16日 的闭包 * 表示 上的一切符号串（包括 ）组成的集合 的正闭包 + 表示 上的 除 外的所有符号串组成的集合 例： =a,b *= ,a,b,aa,ab,ba,bb,aaa,aab, +=a,b,aa,ab,ba,bb,aaa,aab, . 2* . 32* 北京林业大学信息学院 2020年 10月 16日 若 A为某语言的字母表 A a,b,0,1,9, +, , ,_/, ( , ), = if, else,for. B为单词集 B =if, else,for, 则 B A* 。 语言的句子是定义在 B上的符号串。 若令 C为句子集合，则 C B * , 程序 C 为什么对符号、符号串、符号串集合以及它们的运算感兴趣？ 北京林业大学信息学院 2020年 10月 16日 语言 是由句子组成的集合，是由一组符号所构成的集合 字母表 上 的一个语言是 上的一些符号串的集合 字母表 上 的每个语言是 *的一个子集 集合 a,aa,aaa, 或 表示为 w|w *且 w=an,n1 为 字母表 上 的一个语言 例如： 字母表 =a,b , *= ,a,b,aa,ab,ba,bb,aaa,aab, 集合 ab,aabb,aaabbb, ,anbn, 或表示为 w|w *且 w=anbn,n1 为字母表 上 的一个语言 北京林业大学信息学院 2020年 10月 16日 2.2 文法和语言的形式定义 文法 是对语言结构的定义与描述。（或称为“语法”）。 :=“=” :=“+” | “*” :=“(”“)” | | | 北京林业大学信息学院 2020年 10月 16日 赋值语句 标识符 表达式 表达式 表达式 表达式 标识符 整数 标识符 表达式 y = x + r * 6 y = x + r * 6 北京林业大学信息学院 2020年 10月 16日 例：有一句子：“我是大学生” 。 这是一个在语法、 语义上都正确定句子，该句子的结构（称为语法结构）是由 它的语法决定的 。在本例中它为“主谓结构”。 如何定义句子的合法性 ？ 有穷语言：只需逐一列举句子 无穷语言：使用文法定义句子的结构，用适当条数的规 则把语言的全部句子描述出来。文法是以有穷的集 合刻划无穷的集合的工具。 文法的非形式定义 北京林业大学信息学院 2020年 10月 16日 1.语法规则 ：我们通过建立一组规则，来描述句子的语法 结构 。 规定用“ :=”表示“由 组成”。 := :=| :=你 |我 |他 := 王民 |大学生 |工人 |英语 := :=是 |学习 :=| 文法的 BNF表示 北京林业大学信息学院 2020年 10月 16日 2.由规则推导句子 ：有了一组规则之后，可以按照一定的方式 用它们去推导或产生句子。 推导方法：从一个要识别的符号开始推导，即用相应规则的 右部 来替代规则的 左部 ，每次仅用一条规则去进行推导。 = = 这种推导一直进行下去，直到所有带 的符号都由终结符号 替代为止。 北京林业大学信息学院 2020年 10月 16日 = = = 我 =我 =我 是 =我是 =我是 大学生 := :=| :=你 |我 |他 := 王民 |大学生 |工人 |英语 := :=是 |学习 :=| 推导方法： 从一个要识别的符号 开始推导，即用相应规则的 右部 来替代规则的 左部 ， 每次仅用一条规则去进行推导。 北京林业大学信息学院 2020年 10月 16日 例：有一英语句子： The big elephant ate the peanut. := := :=the :=big :=elephant := :=ate := :=peanut 北京林业大学信息学院 2020年 10月 16日 = = = the = the big = the big elephant = the big elephant = the big elephant ate = the big elephant ate = the big elephant ate the = the big elephant ate the peanut := := :=the :=big :=elephant | peanut := :=ate := 北京林业大学信息学院 2020年 10月 16日 上述推导可写成 = the big elephant ate the peanut + 说明： (1) 有若干语法成分同时存在时，我们总是从最左的语法成 分进行推导，这称之为 最左推导 ，类似的有 最右推导 （一般推 导）。 (2) 从一组规则可推出不同的句子，如以上规则还可推出 “大象吃象”、“大花生吃象”、“大花生吃花生”等句子， 它们 在语法上都正确，但在语义上都不正确。 所谓 文法 是在 形式上 对句子结构的定义与描述，而未 涉及 语义 问题。 北京林业大学信息学院 2020年 10月 16日 文法 GS=（ VN， VT， P， S） VN ：非终结符号集 VT ：终结符号集 P： 产生式或规则的集合 S： 开始符号（识别符号） S VN ， S至少要在 一条规则中作为左部出现 V VN VT 称为文法的字母表 补 : 规则的定义 : 或 V+且至少有一个非终结符，而 (VN VT)* 文法的形式定义 北京林业大学信息学院 2020年 10月 16日 G=(VT , VN, S, P)， 其中 : VN=表达式 VT=+,*,(,),i S= 表达式 P= 表达式 表达式 + 表达式 表达式 表达式 * 表达式 表达式 ( 表达式 ) 表达式 i 【 例 2.1】 程序语言中只含 +、 *运算的算术表达式，用 i 表示变量或常数，其文法可以表示为： 描述了表达式的 语法规则 北京林业大学信息学院 2020年 10月 16日 几点说明 ： 产生式左边符号构成集合 VN ，且 S VN 给定一个 文法，实际只需给出产生式集合，并指定识别符号 G表达式 : 表达式 表达式 + 表达式 表达式 表达式 * 表达式 表达式 ( 表达式 ) 表达式 i VN ：代表程序的语法成份，如“表达式”，它不会 出现在程序中 VT ：会出现在程序中，如 i+i 北京林业大学信息学院 2020年 10月 16日 有些产生式具有相同的左部，可以和在一起 GE： EE+E|E*E|(E)|i 北京林业大学信息学院 2020年 10月 16日 GS： SL|SL|SD La|b| |z D 0|1| |9 【 例 2.2】 某种语言的标识符是以字母开头的字母数字 串，如果用 L表示 ， D表示 ，用 S表示字 母数字串 描述了标识符的 词法规则 北京林业大学信息学院 2020年 10月 16日 例：无符号整数的文法： G | 0 | 1 | 2 | 3 | | 9 描述了无符号整 数的词法规则 北京林业大学信息学院 2020年 10月 16日 说明 ： 终结符集是输入字符集，它是构成单词的最基本元素 终结符集是经词法分析识别后的单词集，如变量 i,运 算符 +、 *和分界符 (、 )，它们被视为语法分析中最基 本元素 描述语法规则的文法 GE： EE+E|E*E|(E)|i 描述词法规则的文法 GS： SL|SL|SD La|b|z D0|1|9 北京林业大学信息学院 2020年 10月 16日 文法的表示方法 3.语法图 2. EBNF： 扩充的 BNF的元符号： , :=, |, , , , (, ) 字母 字母 数字 数字 标识符 无符号整数 1. BNF的元符号： , :=, | 北京林业大学信息学院 2020年 10月 16日 推导的形式定义 如果 是文法 G=(VT， VN， S， P)的一个产生式， ， V*，有符号串 x， y满足 x=， y=, 则称 y是 x的 直接推导 ， 也可以说， y直接归约 到 x，记作 x y。 直接推导：用产生式的右部替换产生式的左部 直接归约：用产生式的左部替换产生式的右部的过程 北京林业大学信息学院 2020年 10月 16日 S=SD, 使用规则 SSD ，其中 =； SD=LD,使用规则 SL ，其中 =,=D； LD=aD,使用规则 La ，其中 =,=D； aD=a1, 使用规则 D1 ，其中 =a,=。 GS： SL|SL|SD La|b|z D0|1|9 根据文法和推导的定义，可推出终结符号串 北京林业大学信息学院 2020年 10月 16日 1 1 0 (6) = = (1) = (3) (5) = = (2) 当符号串已没有非终结符号时，推导就必须终止。因为 终结符不可能出现在规则左部，所以将在规则左部出现的符 号称为非终结符号。 例如： G (1) (2) (3) (4) 0 | 1 | 2 | 3 | | 9 北京林业大学信息学院 2020年 10月 16日 如果存在直接推导序列： x y0 y1 y2yn=y 则称这个序列是一个从 x至 y的长度为 n（ n0） 的 推 导 ， 或称 y归约 到 x， 记作 x y。 若有 x y，或 x=y，则记作 x y。 = = * = 例： x S SD LD aD a1=y GS： SL|SL|SD La|b|z D0|1|9 = 记作 x y或记作 x y * = 北京林业大学信息学院 2020年 10月 16日 文法 GS （ 1） 句型 ： x是句型 S ,且 V*； （ 2） 句子 ： x是句子 S , 且 , VT*； （ 3） 语言 ： L（ GS） = | VT*,S ； + + 文法 GS所产生的 所有句子的集合 * 句子是所有终结符 号组成的句型 语言的形式定义 GE： EE+E|E*E|(E)|i 句型： E+E E+E*E E+E*i E+i*i 句子： i+i i*i i+i*i (i+i)*i 北京林业大学信息学院 2020年 10月 16日 形式语言理论可以证明以下两点： （ 1） G L（ G）； （ 2） L(G) G1， G2， ， Gn； 已知文法，求语言，通过推导； 已知语言，构造文法，无形式化方法，更多是凭经验 北京林业大学信息学院 2020年 10月 16日 例： GS S := aSb |ab 求其所产生的语言。 若 S := aSb | ， 如何？ L(GS)=anbn|n1 L(GS)=anbn|n0 已知文法，求语言，通过推导 课堂练习 1： GS S := bA A := aA|a L(GS)=ban|n1 课堂练习 2： GS S := AB A := aA|a B := bB|b L(GS)=ambn|m,n1 北京林业大学信息学院 2020年 10月 16日 例： abna|n1,构造其文法 定义 . G和 G是两个不同的文法，若 L(G) = L(G) , 则 G和 G为 等价文法 。 若 n0，如何？ 课堂练习 3： anbnci |n1,i 0, 构造其文法 GS： S AB A aAb|ab BcB| G1S： SaBa, Bb| bB G2S： SaBa, Bb| Bb G1S： SaBa, B |bB G2S： SaBa, B |Bb 北京林业大学信息学院 2020年 10月 16日 例：构造一个文法，使其描述的语言是无符号整数。 GS： SSD|D D 0|1|2|3|4|5|6|7|8|9 G | 0 | 1 | 2 | 3 | | 9 北京林业大学信息学院 2020年 10月 16日 编译感兴趣的问题是 : 给定 x, G, 求 x L(G) ? x 算法 1 算法 2 x L(G) ? G y n 出错处理 停机 = = 北京林业大学信息学院 2020年 10月 16日 1.递归规则 ：规则右部有与左部相同的符号 左递归规则： AA 右递归规则： AA 自嵌入递归规则： AA 递归文法 2.递归文法 ： 含有递归规则的 文 法，为 直接递归 文 法 ABa BAb GS： SL|SL|SD La|b|z D0|1|9 间接递归 文 法 北京林业大学信息学院 2020年 10月 16日 递归文法的 优点 ：可用有穷条规则，定义无穷语言 例：对于前面给出的无符号整数的文法是有递归文法，用 12 条规则就可以定义出所有的无符号整数。若不用递归文法，那 将要用多少条规则呢？ ! GS： SSD|D D 0|1|2|3|4|5|6|7|8|9 北京林业大学信息学院 2020年 10月 16日 左 递归文法的 缺点 ：不能用自顶向下的方法来进行语法分析 会造成死循环（后面将详细论述） GE： Ei+i|i*i|(i+i)*i 该文法所描述的语言为 L(G)=i+i,i*i,(i+i)*i， 无法表示无穷的表达式语言 北京林业大学信息学院 2020年 10月 16日 2.3 句型的分析 句型的分析： 是指识别输入的符号串是否为某一文法的 句型 (或句子 )的过程 对于同一个句型或句子，可以通过不同的推导序列推导出来， 这是因为在推导过程中所选择的非终结符的次序不同 GE： EE+E|E*E|(E)|i i+i*i的推导序列有哪些？ 北京林业大学信息学院 2020年 10月 16日 最左 (右 )推导指对于一个推导序列中的每一直接推导，被替 换的总是当前符号串中的最左 (右 )非终结符号。最右推导也 称为 规范推导 。 规范推导的逆过程，称为最左归约，也称为 规范归约 。 用最左推导所推导出的句型称为 最左句型 用最右推导所推导出的句型称为 最右句型 ，通常称为 规范句型 规范推导与规范归约 北京林业大学信息学院 2020年 10月 16日 赋值语句 标识符 表达式 表达式 表达式 表达式 标识符 整数 标识符 表达式 y = x + r * 6 语 法 分 析 的 结 果- - 语 法 树 语法树与文法的二义性 北京林业大学信息学院 2020年 10月 16日 1.语法树 ：描述一个句子的语法结构 The big elephant ate the peanut 语法成分（非终 结符） 单词符号（ 终结符号 ) 北京林业大学信息学院 2020年 10月 16日 语法树：句子结构的图示表示法，它是一种有向图，由 结点和有向边组成。 结点 ：符号 根结点： 识别符号 中间结点： 非终结符 叶结点： 终结符或非终结符 有向边 ：表示结点间的派生关系 S U V a b c d 北京林业大学信息学院 2020年 10月 16日 句型推导过程 句型语法树的生长过程 由推导构造语法树 1 从 识别符号 开始， 逐步 建立 推导 序列。 由 根结点 开始， 自上而下 建立 语法树 。 北京林业大学信息学院 2020年 10月 16日 例： G 句型 10 = = 0 0 = 0 = 1 10 = 规范推导 北京林业大学信息学院 2020年 10月 16日 由语法树构造推导 2 自下而上 地修剪子树的末端结点，直至把整棵树剪掉 （留根），每剪一次对应一次规约。 从句型开始， 自右向左 地逐步进行 规约 ，建立推导序列。 北京林业大学信息学院 2020年 10月 16日 0 1 = = 0 = 10 0 = = 规范规约与规范推导互为逆过程 北京林业大学信息学院 2020年 10月 16日 课堂练习： 对于句子 i i * i ，给出两 种不同的规范推导，并画出 语法树 定义 :若一个文法的某句子存在两个不同的 最右 (最左 )推导 ， 则该文法是 二义性 的，否则是无二义性的。 2.文法的二义性 GE： EE+E|E*E|(E)|i 北京林业大学信息学院 2020年 10月 16日 E E E + E E * i i i E E E * E E + i i i 这两种不同的推导对应了两种不同的语法树 (1) E=E+E=E+E*E =E+E*i =E+i*i = i i * i (2) E= E*E = E*i = E+E*i = E+i*i = i i * i 北京林业大学信息学院 2020年 10月 16日 若文法是二义性的，则在编译时就会产生 不确定性 文法的二义性是不可判定的 ，即不可能构造出一个算法， 通过有限步骤来判定任一文法是否有二义性。 可以采用两种途径来解决文法的二义性问题 1 不改变文法中原有的规则，仅加进一些语法的非形式规定。 规定 “ *” 运算优先级高于 “ +”运算，且服从左结合 改写文法，把排除二义性的规则合并到原有文法中 2 北京林业大学信息学院 2020年 10月 16日 E i E T + T F * i F T F i 例 :算术表达式的文法 E:= E+T | T T := T*F | F F := (E) | i GE： EE+E|E*E|(E)|i 北京林业大学信息学院 2020年 10月 16日 2.4 文法和语言的分类 形式语言 (乔姆斯基 )：通过抽象，对语言进行形式化描述 用一组数学符号和规则来描述的语言称为形式语言 *的任何子集称作 上的形式语言 L（ GS） = | VT*,S + 由文法定义语言 文法和语言分类： 0型、 1型、 2型、 3型 这几类文法的差别在于对产生式施加不同的限制。 北京林业大学信息学院 2020年 10月 16日 0型语言： L0 0型文法称为 无约束短语结构文法 。规则的左部和右部都可 以是符号串，一个短语可以产生另一个短语。 0型： P： := 其中 V*且至少含有一个非终结符， V* 北京林业大学信息学院 2020年 10月 16日 0型文法 GS: SABS|AB ABBA A0 B1 L(GS)=x|x是由 n个 01或 10组成的二进制数字串， n1 该文法产生的语言为 北京林业大学信息学院 2020年 10月 16日 SACaB CaaaC CBDB aBBa CBE aDDa ADAC aEEa AE 例： 0型 文法 GS： 北京林业大学信息学院 2020年 10月 16日 1型文法 ： P： A := 其中 A VN， ， V*， V 1型语言： L1 称为 上下文敏感 或 上下文有关 。也即只有在 、 这样的 上下文中才能把 A改写为 北京林业大学信息学院 2020年 10月 16日 SaSBE SaBE BEbE aBab bBbb bEbe eEee 例： 1型（上下文有关） 文法 GS： 北京林业大学信息学院 2020年 10月 16日 2型： P： A:= 其中 A VN ， V* 2型语言： L2 称为 上下文无关文法 。也即把 A改写为 时，不必考虑上下文。 北京林业大学信息学院 2020年 10月 16日 例： 2型（上下文无关）文法 文法 GS： SAB ABS|0 BSA|1 S 北京林业大学信息学院 2020年 10月 16日 （右线性） P： A:=a 或 A:=aB 其中 A、 B VN a VT 3型语言： L3 又称正则语言 . 3型文法称为 正则文法 。它是对 2型文法进行进一步限制。 左线性 和右线性文法是相互等价的 （左线性） P： A:=a 或 A:=Ba 其中 A、 B VN a VT 3型文法： 北京林业大学信息学院 2020年 10月 16日 GS： S0A|1B|0 A0A|1B|0S B1B|1|0 GI： I lT I l T lT T dT T l T d 例： 3型文法 北京林业大学信息学院 2020年 10月 16日 有关文法的实用限制 1、 若文法中有如 U:=U的规则，则这就是 有害规则 ，它会引 起二义性，而无任何用处。 例如存在 U:=U， U:= a | b,则有两棵语法树： U a U U a 文法中不能含有 有害规则 和 多余规则 北京林业大学信息学院 2020年 10月 16日 2、 多余规则 ： （ 1）某条规则 U:=u的左部非终结符 U（ U不是识别符号）， 不在任何其他规则右部出现，即所有的推导始终不会用到此 规则。 （ 2）在推导句子的过程中，一旦使用了该规则，将推不出任 何终结符号串。即该规则中含有推不出任何终结符号串的非 终结符。 例如给定 GS，若其中关于 U的规则 只 有如下一条： U:=xUy 该规则是多余规则。 若还有 U:=a，则此规则 并非多余 若某文法中无有害规则或多余规则，则称该文法是 压缩过的 。 北京林业大学信息学院 2020年 10月 16日 根据上述讨论， L0 L1 L2 L3 0型文法可以产生 L0、 L1、 L2、 L3，但 2型文法只能产 生 L2，不能产生 L1。 2型文法 1型文法 0型文法 3型文法 四种文法之间的逐级“包含”关系 北京林业大学信息学院 2020年 10月 16日 2型文法 （不确定 的下推自动机） 1型文法 （不确定 的界限自动机） 0型文法 （图灵机） 3型文法 （有限 自动机） 形式语言与自动机 北京林业大学信息学院 2020年 10月 16日 图灵机 北京林业大学信息学院 2020年 10月 16日 2.5 PL/0编译程序概述 PL/0编译程序 pcode解释程序 PL/0源程序 pcode代码 PASCAL语言的 子集，功能简单， 结构清晰，可读 性强，具备了一 般高级语言的必 备部分 北京林业大学信息学院 2020年 10月 16日 PL/0语言的功能 （ 1）赋值语句； （ 2）语句串，即 beginend 语句； （ 3）条件语句，即 if语句； （ 4）循环语句，即 while语句； （ 5）过程调用语句，即 call语句； （ 6）输入语句，即 read语句； （ 7）输出语句，即 write语句。 语句类型 北京林业大学信息学院 2020年 10月 16日 （ 1）常量说明（全局） （ 2）变量说明； （ 3）过程说明。 说明类型 数据类型 整型 北京林业大学信息学院 2020年 10月 16日 标识符（字母开始的字母数字串）的有效长度 是 10 数字最多为 14位 过程无参，可嵌套（最多三层）定义，可递归 调用 变量的作用域同 PASCAL 13个保留字： if, then, while, do, read, write, call, begin, end, const, var, procedure, odd 北京林业大学信息学院 2020年 10月 16日 PL/0程序示例 const a=10; var b,c; procedure p; begin c:=b+a end; begin read(b); while b#0 do begin call p; write(2*c); read(b) end end. 不区分大小写 北京林业大学信息学院 2020年 10月 16日 EBNF在此基础上又增加了三种元符号，约定如下： 表示其内语法成分可以重复 例如： AA| ，可改写为： A 。 表示方括号内的成分为任选项； 例如： A| ，可改写为： A 。 ( ) 例如： A1|2|n ， 可改写为： A (1|2|n ) PL/0语言的文法 北京林业大学信息学院 2020年 10月 16日 =+| - =0|1|2|3|4|5|6|7|8|9 =+| -|0 =1|2|3|4|5|6|7|8|9 =0|1|2|3|4|5|6|7|8|9 EBNF示例 北京林业大学信息学院 2020年 10月 16日 PL/0语言文法的 EBNF表示 程序 = 分程序 . 分程序 = 常量说明部分 变量说明部分 过程 说明部分 语句 常量说明部分 =CONST 常量定义部分 ， 常量定义 ； 无符号整数 = 数字 数字 变量说明部分 =VAR 标识符 ， 标识符 ； 标识符 = 字母 字母 | 数字 北京林业大学信息学院 2020年 10月 16日 语句 const ident number = , ; var ident ， procedure ident 分程序 分程序 ; ; ; 分程序 . 程序 语法图 北京林业大学信息学院 2020年 10月 16日 PL/0程序示例改错 var a,b,c; begin read(a,b); c=100 if(a0) thenb=b+1;write(b); else write(c); write(a,b,c); end. 北京林业大学信息学院 2020年 10月 16日 语法语义分析程序 词法分析程 序 表格管理程序 出错处理程序 代码生成程序 PL/0源程序 目标程序 PL/0编译程序的总体设计 读单词 生成目标代码 核 心 一遍扫描方式 北京林业大学信息学院 2020年 10月 16日 编 译 程 序 总 体 流 程 图 启动 置初值 调用GETSYM取单词 调用BLOCK过程 当前单词 是否为源程序结束符 .？ 出错 源程序中 是否有错误？ 调用解释过程INTERPRET 解释执行目标程序 打印错误 结束 N Y Y N 北京林业大学信息学院 2020年 10月 16日 内容： 符号串和符号串集合的运算、文法和语言的定义 几个重要概念：规范推导、规范归约、递归文法、文法的二义性 文法的 BNF、 EBNF、语法图表示 文法和语言的分类 重点： 在理解基本概念的基础上 根据给定的语言写出文法、根据给定的文法确定语言 判断文法的二义性 难点： 关于文法和语言的概念是形式语言的理论基础，形式语言抽象地定 义为一个数学系统 “ 形式 ” 是指：语言的所有规则以符号串的方式来描述。文法就是 这样一个工具 推导，文法与语言的相互转换 小结 北京林业大学信息学院 2020年 10月 16日 习题 2、 3、 4,写在 16开数学作业纸上 作业题 思考题 习题 1、 5-8