课程主页：

https://www.icourse163.org/course/NUDT-1003101005?tid=1460976445

这次回顾第8讲：语法分析——自上而下分析2。

第8讲 语法分析——自上而下分析2(递归下降分析程序)

构造递归下降分析器

  • 分析程序由一组子程序组成， 对每一语法单位(非终结符)构造一个相应的子程序，识别对应的语法单位
  • 通过子程序间的相互调用实现对输入串的识别
    • 例如，$A \to BcD$
  • 文法的定义通常是递归的，通常具有递归结构
  • 定义全局过程和变量
    • ADVANCE：把输入串指示器IP指向下一个输入符号，即读入一个单词符号
    • SYM：IP当前所指的输入符号
    • ERROR：出错处理子程序

递归下降子程序设计

一个简单的例子

对应的递归下降子程序为：

更复杂的例子

  • 现在考虑文法$G(E)$

  • 每个非终结符有对应的子程序的定义，在分析过程中，当需要从某个非终结符出发进行展开(推导)时，就调用这个非终结符对应的子程序。

文法$E→TE′$对应的子程序为：

PROCEDURE E；
    BEGIN
    T；E′
END；

文法${E}^{\prime} \rightarrow+{TE}^{\prime} \mid \varepsilon$对应的子程序为：

PROCEDURE E′；
IF SYM=‘+’ THEN
BEGIN
    ADVANCE；
    	T；E′
END
ELSE IF SYM<>‘#’ AND SYM<>’)’
		THEN ERROR

这一这里使用了如下事实：

文法${T} \rightarrow {FT}^{\prime}$对应的子程序为：

PROCEDURE T；
BEGIN
	F；T′
END

文法${T}^{\prime} \rightarrow {\star} {FT}^{\prime} \mid \varepsilon$对应的子程序为：

PROCEDURE T′；
IF SYM=‘*’ THEN
BEGIN
    ADVANCE；
    F；T′
END
ELSE IF SYM<>‘#’ AND SYM<>’)’ AND SYM<>’+’
	THEN ERROR

文法${F} \rightarrow({E}) \mid {i}$对应的子程序为：

PROCEDURE F；
IF SYM=‘i’ THEN ADVANCE
ELSE
	IF SYM=‘(’ THEN
	BEGIN
        ADVANCE;
        E；
	IF SYM=‘)’ THEN ADVANCE
		ELSE ERROR
    END
    ELSE ERROR;

主程序：

PROGRAM PARSER;
BEGIN
	ADVANCE;
	E;
	IF SYM <>’#’ THEN
		ERROR
END;

扩充的巴科斯范式和语法图

扩充的巴科斯范式

  • 在元符号“$→$”或“$::=$”和“$|$”的基础上，扩充几个元语言符号：

    • 用花括号$\{\alpha\}$表示闭包运算$\alpha^{\star}$。
    • 用$\{α\}_0^n$表示可任意重复$0$次至$n$次。
    • 用方括号$[α]$表示$\{α\}_0^1$，即表示$α$的出现可有可无(等价于$α|ε$)。

  • 例如，通常的“实数”可定义为：

      Decimal→[Sign]Integer.{digit}[Exponent]
Exponent→E[Sign]Integer
  Integer→digit{digit}
  Sign→ + | -

  • 用扩充的巴科斯范式来描述语法，直观易懂，便于表示左递归消去和因子提取。

例子

文法$G(E)$

可表示为

可以用下图清晰表示：

利用巴科斯范式构造递归下降分析程序
PROCEDURE E；
BEGIN
	T；
	WHILE SYM=‘+’ DO
	BEGIN
		ADVANCE；
		T
	END
END；

PROCEDURE  T；
BEGIN
      F；
      WHILE SYM=‘*’ DO
      BEGIN 
           ADVANCE；
           F  
      END
END；

PROCEDURE F；
    IF SYM=‘i’ THEN ADVANCE
    ELSE
        IF SYM=‘(’ THEN
        BEGIN
            ADVANCE;
            E；
            IF SYM=‘)’ THEN
		      ADVANCE
		   ELSE ERROR
	   END
    ELSE ERROR;

JavaCC简介

JavaCC

运行模式如下：

JavaCC包含如下文件，其中后四个文件是不变的：

  • .java
  • Constants.java
  • TokenManager.java
  • ParseException.java
  • SimpleCharStream.java
  • Token.java
  • TokenMgrError.java