文法与语法分析(上)

《文法与语法分析(上)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第04章文法与语法分析主要内容：语法分析概述文法进行语法分析的几种方法语法错误处理4.1语法分析语法分析的任务语法错误类别语法错误的处理语法分析方法分类语法分析的任务：语法错误的发现及处理。语法错误类别：1）开始符和后继符错，语句（表达式）的开始符或后继符错；2）标识符（常量）错：如，该出现时未出现；3）括号类错误：如begin-end，case-end，if-then-else不匹配;4）运算符错：如，赋值语句左部变量后面不是赋值号；5）分隔符错关键性错误是：括号类的配对错。语法错误处理：要求：1）报告错误出现的位置；2）修复错

2、误并继续检查后续部分；3）执行开销不应太大。修改策略：插入/删除/修改如：A:=:=B+C;//删除:=A:=BC;//要插入+应急方式恢复:定义同步符号集合(分隔符，end,某些语句头符，else等)，发现错误时，跳过一些Token，直到找到某个同步符号，再继续进行分析。同步符号保证接下来的分析是从正确的头位置开始。语法分析方法分类分为两大类：[1]自顶向下方法---LL方法、递归下降法；[2]自底向上方法---LR方法（LR(0)，SLR(1)，LR(1)，LALR(1)等）、优先关系法。4.2文法和文法分析语言研究的三个方面

3、：语法--表示构成语言句子的各个记号之间的组合规律语义--表示按照各种表示方法所表示的各个记号的特定含义。（各个记号和记号所表示的对象之间的关系）语用--表示在各个记号所出现的行为中，它们的来源、使用和影响。文法的分类：O型文法:也称为短语文法，其产生式具有形式:→，其中,(VTVN)*，并且至少含一个非终极符。1型文法:也称为上下文有关文法。它是0型文法的特例，要求

4、

5、

6、

7、(S→例外，但S不得出现于产生式右部),其产生式形式:A→。2型文法:也称为上下文无关文法。它是1型文法的特例，即要求产生式

8、左部是一个非终极符:A→。3型文法:也称为正则文法。它是2型文法的特例，即产生式的右部至多有两个符号，而且具有下面形式之一:A→a，A→aB其中A,BVN，aVT。上下文无关文法的定义:G=(VT,VN,S,P)VT是有限的终极符集合；VN是有限的非终极符集合；S是开始符，SVNP是产生式的集合，且具有下面的形式：AX1X2…Xn其中AVN，Xi(VTVN)，右部可空。产生式的书写有如下约定：第一条产生式的左部是开始符号用尖括号括起的是非终结符，否则为终结符。或者大写字母表示非终结符，小写字母表示终结符G可写成G

9、[S]，其中S是开始符号例1：标识符与正整数的文法。

10、

11、

12、

13、0

14、1

15、

16、9A

17、B

18、

19、Z

20、a

21、b

22、

23、z如：x,xy,x3,6,38例2：Pascal语言中“变量”的定义。[]

24、le>.如：x,student.No,x[3],x例3：小语言ToyL的定义

beginend.

25、;id:=

26、write()

27、read(id)id

28、num

29、+

30、*

31、()4.2.2推导及其相关概念推导：如果A是一个产生式，则有A,其中表示一步推导(用A→)。这时称是由A直接推导的。的含义是，使用一条规则，代替左边的某个符号，产生右端的符号

32、串。+:表示通过一步或多步可推导出*:表示通过0步或多步可推导出例4G:<标识符>→<字母><标识符>→<标识符><字母><标识符>→<标识符><数字><字母>→a,…,<字母>→z<数字>→0,…,<数字>→9<标识符><标识符><数字><字母><数字>x<数字>x1即：<标识符>+x1也可记作：<标识符>*x1最左（右）推导：如果进行推导时选择的是句型中的最左(右）非终极符，则称这种推导为最左(右)推导，并用符号lm（rm）表示最左（右）推导。句型：如果有S*，则称符号串为CFG的句型

33、。我们用SF(G)表示文法G的所有句型的集合。句子：如果只包含终极符，则称为CFG的句子，其中S是文法的开始符。例5：已知文法G[S]:S→aAS，A→SbA，A→SS，S→a，A→ba解：1）最右推导：SaASaAaaSbAaaSbb