编译原理学习笔记03
编译原理学习笔记05_解析树和AST

编译原理学习笔记04_LL及谓词解析

nonoob posted @ Wed, 29 Aug 2012 21:32:46 +0800 in Programming , 1494 readers

从现在起正式把《编程语言设计模式》(中文版和英文电子版)加为参考书目。

-----------------------------------------------------

对于一个parser,规范的命名是LL(k),LR(k)之类。LL(k)的含义:第一个L只按从左到有顺序解析输入内容,第二个L表示自顶向下解析时按照从左到右顺序遍历子节点,k表示forward的token为k个。而LL(k)中的r表示的是自底向上解析时按照从右向左推导(从左向右规约)。

LL分析的时候先看到的是产生式左值,然后确定其是由什么右值构成的;于是要做的事就是迭代地匹配产生式,这涉及到了不断地猜测、回溯,通常将A的产生式分为first(A)和follow(A)(和lisp中的car/cdr看起来有些像哈>o<)。这里的“顶”应该是从语法树上看的。LR正好相反,是从产生式的右值开始分析的,开始拿到的是推导式右值中的一个文法(grammar)符号;也可以说是从语法树的叶子节点开始分析。

上下文无关文法(context free grammar)是指没有二义性的文法。一个具有二义性的语法可以参照C++:

T(a)

在只知道T和a是token的情况下,它可能指下面几种情况(或其中一部分):

  1. 函数声明,如int foo(int);
  2. 对象初始化,如Fraction f(42);
  3. 函数调用,如bar(-67);
  4. 强制类型转换,如float(11);

当然在C++手册中规定遇到这种情况声明(a)比表达式(b)(c)(d)优先级较高,所以在构造解析规则的时候通常隐含(用了if-else等分支结构)对解析选项进行了排序,例如:

stat:(declaration)=>declaration
     |expression
      ;

也就是说只要看起来像声明了,就认为是声明;确定不是声明那种货色的了,才考虑它匹配表达式。但问题在于仍然没有办法区分(b)(c)(d)的情况。如果用LL(k)的话,因为在对象初始化前还有一个token(如Fraction),是可以区分(b)和(c)(d)。然而,仅凭这些还是无法区分(c)(d)。事实上这两者的CFG是一样的:

expr:INTEGER
    |ID '(' expr ')'//bar(-67)
    |ID '(' expr ')'//float(11);
     ;

这时就需要采用语义信息了,通常LL(k)是采用形如这样的谓词判断:

void expr() {
if ( LA(1)==INTEGER) match(INTEGER);
else if ( LA(1)==ID && isFunction(LT(1).text) ) «match-function-call »
else if ( LA(1)==ID && isType(LT(1).text) ) «match-typecast »
else «error »
}

在编写解析不同同种语言的解析器是也会用到谓词逻辑;比如gcc的那100+个坑爹的选项,比如java的各个兼容模式……


Login *


loading captcha image...
(type the code from the image)
or Ctrl+Enter