数据库原理与OracleSQL语言

《数据库原理与OracleSQL语言》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Part4语法分析授课：胡静语法分析器的作用以语法分析器为核心的编译器模型语法分析器词法分析器中间代码生成器语义分析器一部分中间代码输入字符串程序入口初始化工作语法分析器的作用接收词法分析器提供的记号串检查记号串是否能由源程序语言的文法产生用易于理解的方式提示语法错误信息，并能从常见的错误中恢复过来语法分析器词法分析器符号表前端的其余部分源程序记号取下一个记号语法树中间表示语法分析器所处的位置语法分析的例子语法分析的类比针对自然语言的语法分析：识别一个句子是不是符合语法规范&识别每一个成分的功能。语法分析器工作原理语言的结构是用

2、上下文无关文法描述的，因此，语法分析器的工作本质上就是按照文法的产生式，识别输入符号串是否为一个句子。语法分析器是从左向右的扫描输入字符串，每次读入一个符号，并判断，看是否能从文法的开始符号出发推导出这个输入串。或者，从概念上讲，就是要建立一棵与输入串匹配的语法分析树。语法分析器分类通用的语法分析方法，用来分析任何文法，生成编译器时效率太低编译器使用的语法分析方法—处理文法的一些子类自顶向下（建立分析树）—LL文法，其分析器常用手工实现自底向上（建立分析树）—LR文法，其分析器常利用自动生成工具构造自顶向下分析面临的困难自顶向下

3、分析面临的困难自顶向下分析的主旨是，对任何输入串，试图用一切可能的办法，从文法的开始符号（根结）出发，自顶向下的为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。这种分析过程本质上是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。自顶向下分析的一般方法是带“回溯”的。自顶向下分析的简单例子假定文法G[S]，以及输入串x*y（记为α）。S→xAyA→**

4、*初始化：第一步扩展Sx*yIPSx*yIPyAx自顶向下分析的简单例子假定文法G[S]，以及输入串x*y（记为α）。S→xAyA→**

5、*第二步扩展：回溯x*y

6、IPSx*yIPyAx**SyAx*自顶向下分析面临的困难文法的左递归性问题。因此，我们要使用自顶向下分析法必须要消除文法的左递归。由于回溯，就碰到一大堆的麻烦事情。如果遇到回溯的情况，就需要把已经作的一大堆语义工作（指中间代码生成工作和各种表格的簿记工作）推倒重来。这些事情既麻烦又费时间，所以，最好设法消除回溯。由于带回溯的自顶向下分析方法实际上采用了一种穷尽一切可能的试探法，因此效率很低。困难我们希望通过读取下一个符号就确定要使用哪一个产生式。S→E+S

7、EE→num

8、(S)这样做很难，这个文法不能够通过向前看一个符号的自顶

9、向下分析方法来进行语法分析LL(1)分析法消除左递归直接左递归的消除P→Pα

10、βP→βP’P’→αP’

11、εE→E+T

12、TT→T*F

13、FF→(E)

14、iE→TE’E’→+TE’

15、εT→FT’T’→*FT’

16、εF→(E)

17、i消除左递归的算法如果一个文法不含回路（形如P=>+P的推导），也不含以ε为右部的产生式，那么执行下述算法将保证消除左递归（但改写后的文法可能含有ε为右部的产生式）。把文法G的所有非终结符按任一种顺序排列成P1,P2,…,Pn；按此顺序执行：FORi:=1TOnDOBEGINFORj:=1TOi-1DO把所有形如Pi

18、→Pjγ的规则改写为：Pi→δ1γ

19、δ2γ

20、…

21、δkγ。其中Pj→δ1

22、δ2

23、…

24、δk是关于Pj的所有规则；消除关于Pi的直接左递归END化简由第2步得到的文法。即去除那些从开始符号出发永远无法到达的非终结符的产生式规则。消除左递归的例子R→Sa

25、aQ→Rb

26、bS→Qc

27、cR→Sa

28、aQ→Sab

29、ab

30、bS→Sabc

31、abc

32、bc

33、cS→abcS’

34、bcS’

35、cS’S’→abcS’

36、εR→Sa

37、aQ→Sab

38、ab

39、bS→abcS’

40、bcS’

41、cS’S’→abcS’

42、εS→Qc

43、cQ→Rb

44、bR→bcaR’

45、caR’

46、aR’R’→

47、bcaR’

48、ε消除回溯、提取左因子为了消除回溯就必须保证：对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候选的工作结果应该是确信无疑的。也就是说，若此候选获得成功匹配，那么这种匹配决不会是虚假的；若此候选无法完成匹配任务，则任何其他候选也肯定无法完成。假定现在轮到非终结符A区执行匹配（或称识别）任务，A共有n个候选α1,α2,…,αn，即A→α1

49、α2

50、…

51、αn。A所面临的第一个输入符号为a，如果A能够根据不同的输入符号指派相应的候选αi作为全权代表去执行任务，那就

52、肯定无需回溯。在这里Ａ已不再是让某个候选去试探性的执行任务，而是根据所面临的输入符号ａ准并的指派唯一的一个候选。消除回溯、提取左因子令Ｇ是一个不含左递归的文法，对G的所有非终结符的每个候选α定义它的终结首符集FIRST(α)为：FIRST(α)={a

53、α=>*a