三、语法分析，《编译原理》（本科教学版），第2版

一、Antlr-v4 设计语法分析器

这个part 主要有两个部分

1. 设计一个类 C语言 Cymbol.g4

   int factorial(int n) {
   	if (n == 1) 
           then return 1;
       
       return n * factorial(n - 1);
   }
   
   int main() {
   	factorial(5);
   }
   

2. 抽取函数调用图（Function Call Graph）

   每个节点是一个函数，如果函数之间有调用关系，就连有向边

   

1.1 Cymbol.g4

1.1 antlr-v4 代码实现

还是很容易看懂的，但是代码中有一些问题需要我们去深究

grammar Cymbol;

@header{
package cymbol;
}

prog : (varDecl | functionDecl)* EOF;

varDecl : type ID ('=' expr)? ';' ;

type : 'int' | 'double' | 'void' ;

functionDecl : type ID '(' formalParameters? ')' block ;

formalParameters : formalParameter (',' formalParameter)* ;

formalParameter : type ID ;

block : '{' stat* '}' ;

stat : block
     | varDecl
     | 'if' expr 'then' stat ('else' stat)?
     | 'return' expr? ';'
     | expr '=' expr ';'
     | expr ';'
     ;

expr : ID '(' exprList? ')'
     | expr '[' expr ']'
     | '-' expr
     | '!' expr
     | expr '^' expr
     | expr ('*' | '/') expr
     | expr ('+' | '-') expr
     | expr ('==' | '!=') expr
     | '(' expr ')'
     | ID
     | INT
     ;

exprList : expr (',' expr)* ;

// 词法结构
SEMI : ';' ;
COMMA : ',' ;
LPAREN : '(' ;
RPAREN : ')' ;
LBRACK : '[' ;
RBRACK : ']' ;
LBRACE : '{' ;
RBRACE : '}' ;

IF : 'if' ;
THEN : 'then' ;
ELSE : 'else' ;
RETURN : 'return' ;

INTTYPE : 'int' ;
DOUBLETYPE : 'double' ;
VOIDTYPE : 'void' ;

ADD : '+' ;
SUB : '-' ;
MUL : '*' ;
DIV : '/' ;

EQ : '=' ;
NE : '!=' ;
EE : '==' ;

WS  : [ \t\n\r]+ -> skip ;

ID : LETTER (LETTER | DIGIT)* ;
INT : DIGIT+ ;

fragment LETTER : [a-zA-Z] ;
fragment DIGIT : [0-9] ;

1.2 二义性

我们下面看一些比较经典的二义性文法的例子：

1.2.1 悬空的else

stat : 'if' expr 'then' stat
     | 'if' expr 'then' stat 'else' stat
     | expr
     ;

上面是对于 if-else 分支的一个 .g4 文件的描述

但是我们发现尝试解释下面这个语句：

		if a then if b then c else d
解释1:   if [a] then [if b then c] else d
解释2:   if [a] then [if b then c else d]

两种解释的语义不同，会导致我们程序的结果不同

龙书上给出了非常难懂的消除二义性文法后的定义：

grammar IfStatOpenMatched;

@header {
package ifstat.ifstatopenmatched;
}

prog : stat EOF ;

stat : matched_stat | open_stat ;

matched_stat : 'if' expr 'then' matched_stat 'else' matched_stat
             | expr
             ;

open_stat: 'if' expr 'then' stat
         | 'if' expr 'then' matched_stat 'else' open_stat
         ;

expr : ID ;

ID : [a-z] ;
WS : [ \t\n\r]+ -> skip ;

而 antlr-v4 并没有选择上面的方式，而是选择使用最前优先匹配原则来解决这一点：

if a then if b then c else d
解释:   if [a] then [if b then c else d]

我们在 IDE 中测试一下：

1.2.2 运算符结合性带来的二义性

Expr.g4

@grammar Expr;

@header {
package expr;
}

prog : expr EOF ;

expr :
     | expr '*' expr
     | expr '-' expr
     | DIGIT
     ;

DIGIT : [0-9] ;
WS : [ \t\n\r]+ -> skip ;

如果我们对于 1-2-3 进行解释：

解释1: 1-[2-3]
解释2: [1-2]-3

我们发现出现了左结合右结合的问题

在 IDE 中运行一下：

antlr-v4 的做法是默认 左结合

但是我们在文法中如何显示自定义声明呢？

比如我们在之前的 Cymbol.g4 中想要声明 幂运算^ 为右结合，就可以像下面这样：

加上 <assoc = right>

expr : ID '(' exprList? ')'
     | expr '[' expr ']'
     | '-' expr
     | '!' expr
     | <assoc = right> expr '^' expr
     | expr ('*' | '/') expr
     | expr ('+' | '-') expr
     | expr ('==' | '!=') expr
     | '(' expr ')'
     | ID
     | INT
     ;

再看一个运算符结合性的问题：

右结合运算符、前缀运算符与后缀运算符的结合性

grammar ExorAssoc;

expr : '!' expr
     | <assoc = right> expr '^' expr
     | DIGIT
     ;

DIGIT : [0-9] ;
WS : [ \t\n\r]+ -> skip ;

显然对于这类运算符只会有一种情况，不会产生二义性

antlr-v4 解释：

1.2.3 运算符的优先级带来的二义性

Expr.g4

grammar Expr;

@header {
package expr;
}

prog : expr EOF ;

expr :
     | expr '*' expr
     | expr '-' expr
     | DIGIT
     ;

DIGIT : [0-9] ;
WS : [ \t\n\r]+ -> skip ;

antlr-v4 可以轻松处理该文法：

我们也可以通过左递归的方式来解决：

grammar ExprLR;

@header{
package expr;
}

prog : expr EOF ;

expr : expr '-' term
     | term
     ;

term : term '*' factor
     | factor
     ;

factor : DIGIT;

DIGIT : [0-9] ;
WS : [ \t\n\r]+ -> skip ;

我们也可以通过右递归的方式来解决：

grammar ExprRR;

@header {
package parserantlr.expr;
}

prog : expr EOF ;

expr : term expr_prime ;
expr_prime : '-' term expr_prime
           |
           ;

term : factor term_prime ;
term_prime : '*' factor term_prime
           |
           ;

factor : DIGIT ;

DIGIT : [0-9] ;
WS : [ \t\n\r]+ -> skip ;

但是有递归文法有一个问题就是：他把减法解释成了右结合：

1.3 函数调用图

antlr-v4 如何根据 Cymbol.g4 的内容来自动生成一棵语法分析树。

上面这个函数调用图的对应代码：

int main() {
  fact();
  a();
}

double fact(int n) {
  print(n);

  if (n == 0)
  then return 1;

  return n * fact(n - 1);
}

void a() {
  int x = b();
  if false
  then {
    c();
    d();
  }
}

void b() {
  c();
}

void c() {
  b();
}

void d() {

}

void e() {

}

我们在 IDEA 中创建项目时勾选上 gradle，在gradle.build 中 的 plugins 和 dependencies 中添加如下内容：

plugins {
    id 'antlr'
}

dependencies {
    // https://mvnrepository.com/artifact/org.antlr/antlr4
    antlr 'org.antlr:antlr4:4.13.1'
}

gradle同步后在右侧的gradle 工具栏中 选择generateGrammarSource 后，就会自动生成一系列的 java文件

生成的 java 文件我们只需复写几个类的方法，也就几行代码，antlr-v4 就能生成我们想要的语法分析树了

（注意如果想要生成一摸一样的语法树，应该在添加了备选分支声明后再去调用generateGrammarSource，详见下面几行）

CymbolParser 就是根据我们给出的Cymbol.g4 如何构建出我们想要的那个语法树。

我们先不管语法树如何构建，这里我们关心 CymbolBaseListener

antlr-v4 是如何根据 语法树从而处理复杂的语法的。

ParseTreeWalker 负责以 DFS 的方式自动遍历语法树。

而 Listener 负责监听 进入，进出事件

关于监听器模式：

做过一些需要 GUI 的小项目的话（比如 基于QT 的项目）其实不会陌生， 我们 按钮点击后如何触发对应的事件逻辑的呢？

其实背后就是一个 listener 一直在监听这个按钮点击事件，监听到后触发对应逻辑

而我们前面的文法定义，因为备选分支过多，可能因为各种原因而产生二义性，这些备选分支就是语法树上的节点

antlr-v4 允许我们显示声明备选分支的名称：

stat : block    # BlockStat
     | varDecl  # VarDeclStat
     | 'if' expr 'then' stat ('else' stat)? # IfStat
     | 'return' expr? ';'   # ReturnStat
     | expr '=' expr ';'    # AssignStat
     | expr ';' # ExprStat
     ;

expr: ID '(' exprList? ')'    # Call // function call
    | expr '[' expr ']'       # Index // array subscripts
    | op = '-' expr                # Negate // right association
    | op = '!' expr                # Not // right association
    | <assoc = right> expr '^' expr # Power
    | lhs = expr (op = '*' | op = '/') rhs = expr     # MultDiv
    | lhs = expr (op = '+' | op = '-') rhs = expr     # AddSub
    | lhs = expr (op = '==' | op = '!=') rhs = expr  # EQNE
    | '(' expr ')'            # Parens
    | ID                      # Id
    | INT                     # Int
    ;

格式就是 " #: 名称 "

生成的 CymbolListener.java中是对于 CymbolListener.java 这个 interface 的 定义，提供了很多空方法，我们事实上只需复写其中的：

enterFunctionDecl 和 enterCall 方法即可

因为是树形结构，我们封装一个Graph类先：

• addNode：添加一个节点
• addEdge：从调用函数向被调用函数连边
• toDot：根据图中存的树来生成.dot文件（模板代码不用管）

package cymbol.callgraph;

import org.antlr.v4.runtime.misc.MultiMap;
import org.antlr.v4.runtime.misc.OrderedHashSet;

import java.util.Set;

public class Graph {
  private final Set<String> nodes = new OrderedHashSet<>();
  private final MultiMap<String, String> edges = new MultiMap<>();

  public void addNode(String node) {
    nodes.add(node);
  }

  public void addEdge(String caller, String callee) {
    edges.map(caller, callee);
  }

  public String toDot() {
    StringBuilder buf = new StringBuilder();

    buf.append("digraph G {\n")
        .append("  ranksep = 0.25;\n")
        .append("  edge [arrowsize = 0.5]\n")
        .append("  node [shape = circle, fontname = \"ArialNarrow\", fontsize = 12, fixedsize = true, height = 0.45];\n");

    buf.append("  ");
    nodes.forEach(node -> buf.append(node).append("; "));
    buf.append("\n");

    edges.getPairs().forEach(edge ->
        buf.append(" ")
            .append(edge.a)
            .append(" -> ")
            .append(edge.b)
            .append(";\n"));
    buf.append("}\n");

    return buf.toString();
  }
}

然后创建 FunctionCallGraphListener 类，继承 CymbolListener，然后复写 enterFunctionDecl 和 enterCall 这两个方法

package cymbol.callgraph;

import cymbol.CymbolBaseListener;
import cymbol.CymbolParser;

public class FunctionCallGraphListener extends CymbolBaseListener {
  private Graph graph = new Graph();
  public Graph getGraph() {
    return graph;
  }

  private String currentFunction;

  @Override
  public void enterFunctionDecl(CymbolParser.FunctionDeclContext ctx) {
    currentFunction = ctx.ID().getText();
    graph.addNode(currentFunction);
  }

  @Override
  public void enterCall(CymbolParser.CallContext ctx) {
    String callee = ctx.ID().getText();
    graph.addEdge(currentFunction, callee);
  }
}

• enterFunctionDecl：我们拿到新发现的函数 ctx 的函数名 并赋值给 currentFunction，然后加入到 graph 的节点集合
• enterCall：从当前函数 currentFunction 向 被调用函数 ctx 连边

然后我们可以写一个程序来生成我们想要的那个 函数调用图了：

• 创建一个 CymbolParser对象 parser
• 调用 parser 的 prog 方法 对输入进行分析 得到 ParseTree 对象 tree
• 创建一个 ParseTreeWalker 对象 walker 来遍历 tree
• 将 walker.toDot 输出到 我们最终的 dot 文件中

CallGraph.java

package cymbol.callgraph;

import org.antlr.v4.runtime.CharStream;
import org.antlr.v4.runtime.CharStreams;
import org.antlr.v4.runtime.CommonTokenStream;
import org.antlr.v4.runtime.tree.ParseTree;
import org.antlr.v4.runtime.tree.ParseTreeWalker;

import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.nio.file.Files;
import java.nio.file.Path;

import cymbol.CymbolLexer;
import cymbol.CymbolParser;

public class CallGraph {
  public static void main(String[] args) throws IOException {
    InputStream is = new FileInputStream(Path.of("src/main/antlr/cymbol/cymbol-functioncall.txt").toFile());
    CharStream cs = CharStreams.fromStream(is);
    CymbolLexer lexer = new CymbolLexer(cs);
    CommonTokenStream tokens = new CommonTokenStream(lexer);

    CymbolParser parser = new CymbolParser(tokens);
    ParseTree tree = parser.prog();

    ParseTreeWalker walker = new ParseTreeWalker();
    FunctionCallGraphListener fc = new FunctionCallGraphListener();
    walker.walk(fc, tree);

    Path fileName = Path.of("src/main/antlr/cymbol/functioncall.dot");
    Files.writeString(fileName, fc.getGraph().toDot());
  }
}

最终效果：

1.4 walker 的 时机

我们上面复写了 enterFunctionDecl 和 enterFunctionCall ，我们能否改成exitFunctionDecl 和 exitFunctionCall呢？

进入时一无所知，退出时其子树已经遍历完，获得了更多信息

但是具体要看我们选择的时机能否完成我们要做的事情。

1.5 ParseTreeWalker 与 Listener

public void walk(ParseTreeListener listener, ParseTree t) {
    if (t instanceof ErrorNode) {
        listener.visitErrorNode((ErrorNode)t);
        return;
    } else if(t instanceof TerminalNode) {
        listener.visitTerminal((TerminalNode)t);
        return;
    }
    RuleNode r = (RuleNode)t;
    	enterRule(listener, r);
    	int n = r.getChildCount();
    	for (int i = 0; i < n; ++ i)
            walk(listener, r.getChild(i));
    exitNode(listener, r);
}

ParseTreeWalker 的work逻辑：

• 如果是错误节点，那么进入错误处理逻辑
• 如果是终止节点，那么进入终止处理逻辑
• 否则的话，调用enter逻辑，我们对 t 进行dfs，结束后，调用exit逻辑
  • enterNode 和 exitNode 就是我们复写的方法进行了封装

二、上下文无关法

这一part 我们将介绍一种用于描述程序设计语言语法的表示方法——“上下文无关文法”或者简称“文法”。

文法自然地描述了大多数程序设计语言构造的层次化语法结构。例如，Java中的 if-else 语句通常具有如下形式：

if (expression) statement else statement

即 一个 if-else 语句由关键字 if、左括号、表达式、右括号、一个语句、关键字 else 和 另一个语句连接而成。

如果我们用 expr 来表示表达式，用变量 stmt 表示语句，那么这个构造规则可以表示为：

stmt -> if (expr) stmt else stmt

其中的箭头(->) 可以读作 “可以具有如下形式”。这样的规则称为产生式（production）。

在一个产生式中，像关键字 if 和括号这样的词法元素称为终结符号(terminal)。像 expr 和 stmt 这样的变量表示终结符号的序列，它们称为 非终结符号(nonterminal)

2.1 定义

**一个上下文无关文法(Context-Dree Grammar，CFT)**是一个四元组 G = (T, N, S, P)：

• 终结符号（T）是组成串的基本符号。术语“词法单元名字”是“终结符号”的同义词。

• 非终结符号（N）是表示串的集合的语法变量。前面的 stmt 和 expr 是非终结符号。非终结符号表示的串集合用于定义由文法生成的语言。非终结符号给出了语言的层次结构，而这种层次结构是语法分析和翻译的关键。

• 在一个文法中，某个非终结符号被指定为开始符号（S）。这个符号表示的串集合就是这个文法生成的语言。按照惯例，首先列出开始符号的产生式。

• 一个文法的**产生式（P）**描述了将终结符号和非终结符号组合成串的方法。每个产生式由下列元素组成：

  • $$\begin{array}{rl}& A\in N\to \alpha \in (T\cup N)\ast \end{array}$$

  • **头部/左部(Head) A：**单个非终结符

  • 体部/右部(Body) α：终结符和非终结符构成的串，也可以是空串 ε

示例：

E -> E + E | E * E | (E) | -E | id

E -> TE'
E' -> +TE' | ε
T -> FT'
T' -> *FT' | ε
F -> (E) | id

S -> aSa
S -> bSb
S -> a
S -> b
S -> c

而之前我们用antlr 写的 Cymbol 中还有如下写法：

functionDecl : type ID '(' formalParameters? ')' block ;

formalParameters : formalParameter (',' formalParameter)* ;

formalParameter : type ID ;

block : '{' stat* '}' ;

stat : block
     | varDecl
     | 'if' expr 'then' stat ('else' stat)?
     | 'return' expr? ';'
     | expr '=' expr ';'
     | expr ';'
     ;

我们上面出现了 * ?，当然我们也可以加入 +

这些符号严格不在上下文无关文法的定义中，事实上 +、*、? 被称为 扩展 BNF 范式

+、*、? 实际上是一种简写

比如 * 可以写成：

stats : stat stats
	  | ε
	  ;

语法树

设G是给定的语法，称满足下列条件的 树为G的一棵语法树:

• 树的每个节点都标有G的一个语法符号，且根节点标有初始符S。
• 如果一个非叶节点A按从左到右顺序有n个儿子节点B1, B2, …, Bn，则: A→B1B2…Bn 一定是G的一个产生式

因为antlr 会帮我们生成 语法树, 所以这个概念应该不会陌生, 只不过这里 用文法的概念加以解释.

语法树反映出我们的推导过程, 十分有用.

2.2 语义

2.2.1 递归

设有文法G

• 直接左递归: 若有E→Eα形式的规则，则 称E是直接左递归。
• 直接右递归: 若有E→αE形式的规则，则 称E是直接右递归。
• 左递归: 若有 E->Eα, 则称 E 是 左递归文法
• 右递归: 若有 E->αE, 则称 E 是 右递归文法
• 递归: E -> αEβ

2.2.2 推导

语义：上下无关文法 G 定义了一个 语言 L(G)

而语言是 *串 的集合，串从何来？

推导(Derivation)

E -> E + E | E * E | -E | id

推导即是将某个产生式的左边替换成它的右边

每一步推导需要选择替换哪个非终结符号，以及使用哪个产生式

E => -E => -(E) => -(E + E) => -(id + E) => -(id + id)

如果推导过程中，每一步都选择最左侧的非终结符进行推导，我们称这是 Leftmost（最左）Derivation，否则称 Rightmost（最右）Derivation

下面是一些定义：
$$如果S\stackrel{\ast }{\Rightarrow }\alpha ，且\alpha \in (T\cup N{)}^{\ast },则称\alpha 是文法G的一个句型$$

$$如果S\stackrel{\ast }{\Rightarrow }w,且w\in T^{\ast },则称w是文法G的一个句子$$

文法 G 的 语言 L(G) 是它能够推导出的 所有句子 构成的集合。
L ( G ) = { w ∣ S ⇒ ∗ w } L(G) = \{w | S\overset{*}\Rightarrow w\} L(G)={w∣S⇒∗w}
关于文法 G 的 两个基本问题：

• Membership问题：给定字符串 $x\in T^*, x \in L(G) ? $
  • 这就是语法分析器的任务：为输入的词法单元流寻找推导、构建语法分析树,或者报错
• L(G) 究竟是什么
  • 这是程序设计语言设计者需要考虑的问题

下面看几个问题2的例子：

S -> SS
S -> (S)
S -> ε
L(G) 是一个良匹配括号串

S -> Sab
S -> ε
L(G) = {a^nb^n | n >= 0}

再看几个问题1的例子：

字母表∑ = { a, b } 上的所有回文串(Palindrome)构成的语言

S -> aSa
S -> bSb
S -> a
S -> b
S -> c

{ b n a m b 2 n ∣ n ≥ 0 , m ≥ 0 } \begin{align} \{b^na^mb^{2n} | n\ge0,m\ge0\} \end{align} {bnamb2n∣n≥0,m≥0}​​

S -> bSbb | A
A -> aA | ε

{ x ∈ { a , b } ∗ ∣ x 中 a , b 个数相同 } \{x \in \{a, b\}^* | x 中 a, b个数相同 \} {x∈{a,b}∗∣x中a,b个数相同}

两种写法：
写法一：V -> aVb | bVa | ε | VV
写法二：V -> aVbV | bVaV | ε

{ x ∈ { a , b } ∗ ∣ x 中 a , b 个数不同 } \{x\in \{a, b\}^* | x 中 a, b 个数不同\} {x∈{a,b}∗∣x中a,b个数不同}

S -> T | U
T -> VaT | VaV
U -> VbU | VbV
V -> aVbV | bVaV | ε

L = { a n b n c n ∣ n ≥ 1 } L = \{a^nb^nc^n | n\ge 1\} L={anbncn∣n≥1}

S -> aBC
S -> aSBC

CB -> CZ
CZ -> WZ
WZ -> WC
WC -> BC

aB -> ab
bB -> bb
bC -> bc
cC -> cc

这个最复杂：每次S递归展开会多一个前缀a，后缀BC，中间四行能够让所有的B移动到C前面，保证了 a，b，c数目相等且顺序合法
L = { a n b m c k ∣ m = n + k , n ≥ 1 , m ≥ 1 , k ≥ 1 } L = \{a^nb^mc^k | m=n+k, n\ge1, m\ge1, k\ge 1\} L={anbmck∣m=n+k,n≥1,m≥1,k≥1}

S = AB
A = aAb|ab
B = bBc|bc

2.2.3 二义性

前面的antlr 中已经介绍了二义性.

很可惜的是, 目前不存在一般性的方法来判断二义性

对二义性文法进行修改，消除其二义性会导致文法的复杂程度和符号数目迅速升高。
但是可以利用二义性文法状态少，分析快的特点，使用二义性文法，对具体问题加入语义规则，约束其二义性即可。

比如我们antlr 中有着 最前匹配, 最长匹配规则等

2.3 与 正则表达式比较

为什么不使用优雅、强大的正则表达式描述程序设计语言的语法?

正则表达式的表达能力严格弱于上下文无关文法

每个 正则表达式 r 对应的语言 L® 都可以使用上下文无关文法来描述

例如：r = (a | b)* abb

它有如下 NFA：

我们 将每个节点标记为 Ai

那么可以构造如下等价文法：

A0 -> aA0 | bA0 | aA1
A1 -> bA2
A2 -> bA3
A3 -> ε

此外，δ(Ai, ε) = Aj，则添加 Ai -> Aj

这只是说明了 正则表达式的能力不强于文法，我们下面证明严格弱于文法

下面是 L = {a^n, b^n | n >= 0} 的文法描述

S -> aSb
S -> ε

该语言无法用正则表达式来描述

反证法：

假设存在正则表达式 r：L® = L = {a^nbn | n >= 0}

则存在有限状态自动机 D®: L((D®) = L; 设其状态数为 k >= 1

我们考虑输入 a^m (m >= k)

由于 m >= k，根据鸽巢原理，一定存在两个状态为同一状态

如果我们输入 aibi，那么能够到达一个接受状态

而由于 我们已知一定存在两个状态为同一状态，那么一定存在 a^{i + j}b^i 也到达接受状态，而 a^{i + j}b^i 显然是不属于上面这个语言的

故矛盾，得证

其实有这样一个定理来证明 正则表达式的描述能力严格弱于 上下文无关文法：

Pumping Lemma for Regular Languages

(条件3类似于我们前面鸽巢原理的分析）

使用方式就是 找一个 length >= p 的 s，满足条件1、2，3，然后我们想办法去找矛盾。

通常使用方式是找一个串满足前两个条件，让其违反第三个条件

给一个例子：
D = { 1 n 2 ∣ n ≥ 0 } i s   n o t   a   r e g u l a r . 证明： 考虑 s = 1 p 2 ( p i s t h e p u m p i n g l e n g t h ) ∣ s ∣ ≥ p s = x y z x y 2 z ∈ D p 2 < ∣ x y 2 z ∣ + ∣ y ∣ ≤ p 2 + p < p 2 + 2 p + 1 = ( p + 1 ) 2 这说明 p 2 < ∣ x y 2 z ∣ < ( p + 1 ) 2 ，所以 ∣ x y 2 z ∣ ∉ D ，矛盾，故 D 不是 r e g u l a r \begin{align} & D = \{1^{n^2} | n \ge 0\} is \ not \ a \ regular. \\ & 证明： \\ & 考虑 s = 1^{p^2} (p is the pumping length) \\ & |s| \ge p \\ & s = xyz \\ & xy^2z \in D \\ & p^2 \lt |xy^2z| + |y| \le p^2 + p \lt p^2 + 2p + 1 = (p+1)^2 \\ & 这说明p^2 \lt |xy^2z| \lt (p + 1)^2，所以 |xy^2z| \notin D，矛盾，故D不是regular \end{align} ​D={1n2∣n≥0}is not a regular.证明：考虑s=1p2(pisthepumpinglength)∣s∣≥ps=xyzxy2z∈Dp2<∣xy2z∣+∣y∣≤p2+p<p2+2p+1=(p+1)2这说明p2<∣xy2z∣<(p+1)2，所以∣xy2z∣∈/D，矛盾，故D不是regular​​
回看这张图：

上下文无关文法能力的界限在哪？

比如下面这个就描述不了

如何证明？

同样有适用于 上下文无关文法的 Pumping Lemma theory

三、自顶向下的语法分析

我们有一个很重要的任务就是去构建语法分析树。

大致有两种方法：自顶向下 / 自底向上

我们只考虑无二义性的文法。即，每个句子对应唯一的一棵语法分析树。

下面将介绍：LL(1)语法分析器

LL(1) 语法分析器：自顶向下的、递归下降的、基于预测分析表的、适用于 LL(1) 文法 的 LL(1) 语法分析器。

自顶向下构建语法分析树，根节点是文法的起始符号 S，每个中间节点表示对某个非终结符应用某个产生式进行推导。

• 问题是：选择哪个非终结符，以及选择哪个产生式

叶节点是词法单元流 w$，仅包含终结符号与特殊的文件结束符$(EOF)

3.1 LL(1) 文法

每个中间节点表示对某个非终结符应用某个产生式进行推导

**Q：**选择哪个非终结符，以及选择哪个产生式

在推导的每一步中，LL(1) 总是选择 最左边的非终结符进行展开

LL(1)：从左向右读入词法单元

递归下降的典型实现框架

void A(){
    选择一个产生式, A->X1X2...Xk;
    for(i = 1 to k) {
        if (Xi是一个非终结符号)
            调用过程Xi();	// 递归下降调用其它非终结符对应的递归函数
        else if(Xi等于当前的输入符号a)	// 匹配当前词法单元
            读入下一个输入符号;
        else /*发生了错误*/
            ;
    }
}

为每个非终结符写一个递归函数

内部按需调用其它非终结符对应的递归函数，下降一层

我们下面演示递归下降过程，每次都选择最左边的非终结符展开

S -> F
S -> (S + F)
F -> a

为什么前两次选择了 S -> (S + F) 而第三次选择了 S -> F？

因为它们面对的当前词法单元不同

我们如果有一张表，即 预测分析表，来帮助我们确定产生式，那么问题就会大大简化。

比如上图就是我们给出示例的预测分析表，指明了每个非终结符在面对不同的词法单元或文件结束符时该选择哪个产生式(按编号进行索引)或者报错(空单元格)。

我们现在可以给出LL(1)文法的定义：

如果文法 G 的 预测分析表 是无冲突的，则G是LL(1)文法。

无冲突：每个单元格内只有一个产生式（编号）

对于当前选择的非终结符，仅根据输入中当前的词法单元(LL(1))即可确定需要使用哪条产生式。

显然是存在非LL(1)文法的：

LL(1)文法 只需要看当前词法单元即可确定产生式的选择，而下面这个我们至少要看三个词法单元才可以，所以下面这个是 LL(3) 文法

S -> abC | abC
C -> c | d

以及我们前面分析二义性时，那个表达式文法也不是LL(1)的：

3.2 递归下降的、基于预测分析表的实现方法

S -> F
S -> (S + F)
F -> a

仍以上面的文法为例

procedure S()
	if token = '(' then 
       	MATCH('(')
        S()
        MATCH('+')
        F()
        MATCH(')')
    else if token = 'a' then
        F()
    else
        ERROR(token, {'(', 'a'})
procedure MATCH(t)
    if token = t then
        token <- NEXT-TOKEN()
    else
        ERROR(token, t)
        
procedure F()
    if token = 'a' then
        MATCH('a')
    else
        ERROR(token, {'a'})

3.3 预测分析表的获取

3.3.1 FIRST 和 FOLLOW

FIRST(α) 是可从 α 推导得到的句型的首终结符号的集合。
$$
\begin{align}
& 对于任意的(产生式的右部)\alpha \in (N \cup U)^* :\
& FIRST(\alpha) = {t\in T\cup {\epsilon}| \alpha \xRightarrow{} t\beta \or \alpha \xRightarrow{}\epsilon }

\end{align}
$$
考虑非终结符 A 的所有产生式 A->α1, A->α2,…,A->αm, 如果它们对应的FIRST(α)集合互不相交, 则只需查看当前输入词法单元,即可确定选择哪个产生式**(或报错)**.

FOLLOW(A) 是可能在某些句型中紧跟在A右边的终结符的集合
$$
\begin{align}
& 对于任意的(产生式的左部)A \in N :\
& FOLLOW(A) = {t\in T\cup {$}| \exist s. S\xRightarrow{*} s \overset{\Delta}= \beta At\gamma }.

\end{align}
$$
考虑产生式 A -> α, 如果 α 可能推导出空串($\alpha \stackrel{\ast }{\Rightarrow }ϵ$), 只有当当前词法单元 t ∈ FOLLOW(A), 才可以选择该产生式.

有了FIREST(α) 和 FOLLOW(α) 的 概念以后, 我们就可以尝试构造预测分析表:

3.3.2 FIRST 的计算

先计算每个符号 X 的 FIRST(X)集合

• 如果X是终结符, 那么 FIRST(X) = {X}
• 对于 某个 a, 如果 a 在 某个 FIRST(Yi), 并且 ε 在 所有 FIRST(Y1,2,…,i - 1)中, 我们才能将 a 加入, 即 对于 一个 FIRST(Yi), 他能加入FIRST(X) 当且仅当前面的 产生式都能推导出空
• 如果 X -> ε 是一个产生式, 那么将 ε 加入到 FIRST(X) 中

procedure FIREST(X)
    if X ∈ T then	// 规则1: X是终结符
        FIRST(X) = {X}
	
	for X -> Y1Y2...Yk do	// 规则2: X是非终结符
        FIRST(X) <- FIRST(X) ∪ {FIRST(Y1)\ {ε}}
		for i <- 2 to k do
            if ε ∈ L(Y1... Yi-1) then
                FIRST(X) <- FIRST(X) ∪ {FIRST(Yi)\ {ε}}
		if ε ∈ L(Y1...Yk) then	// 规则3: X可推导出空串
            FIRST(X) <- FIRST(X) ∪ {ε}

不断应用上述规则, 直到 每个 FIRST(X) 都不再变化(不动点!!!)

下面做个练习:

FIRST(X) = {a, c, ε}

FIRST(Y) = {c, ε}

FIRST(Z) = {a, c, d}

FIRST(XYZ) = {a, c, d}

为什么 ε 不在 FIRST(Z) 和 FIRST(XYZ) 中?

Z -> XYZ, 而 ε 在 X 和 X 中, 然后我们要判断 是否 ε 是否在 Z中, 而此时 Z只能->d, 所以 ε 不能加入 FIRST(Z), 也不能加入 FIRST(XYZ) 中

3.3.3 FOLLOW 的计算

先计算每个符号 X 的 FOLLOW(X)集合

• 如果 X 是开始符号, 那么将 输入右端的结束标记加入 FOLLOW(X)
• 如果存在一个产生式 A->αXβ, 那么 FIRST(β) 中除 ε 之外的所有符号都在 FOLLOW(X) 中
• 如果存在一个产生式 A->αX, 或存在产生式A->αXβ 且 FIRST(β) 包含ε, 那么 FOLLOW(A) 中的所有符号都在 FOLLOW(X)中

procedure FOLLOW(X)
    for X 是开始符号 do	// 规则1: X是开始符号
        FOLLOW(X) <- FOLLOW(X) ∪ {$}
	
    for A -> αX do	// 规则2: X 是 某产生式右部的最后一个符号
        FOLLOW(X) <- FOLLOW(X) ∪ FOLLOW(A)
        
    for A -> αXβ do	// 规则3: X 是 某产生式右部中间的一个符号
        FOLLOW(X) <- FOLLOW(X) ∪ (FIRST(β) \ {ε})
        if ε ∈ FIRST(β) then
            FOLLOW(X) <- FOLLOW(X) ∪ FOLLOW(A)

不断应用上面的规则，直到每个 FOLLow(X)都不再变化**(不动点!!!)**

做个练习:

FOLLOW(X) = {$, a, c, d}

FOLLOW(Y) = {a, c, d, ε}

FOLLOW(Z) = $\varnothing$

为什么FOLLOW(Z) 为空?

应用规则2, 那么 FOLLOW(Z) <- FOLLOW(Z) ∪ FOLLOW(Z)

规则3无法应用

3.3.4 根据 FIRST 和 FOLLOW 集合 计算给定文法 G 的预测分析表

对应每条产生式 A->α 与 终结符 t, 如果
KaTeX parse error: Undefined control sequence: \and at position 85: …arrow \epsilon \̲a̲n̲d̲ ̲t \in FOLLOW(A)…
则在表格 [A, t] 中填入 A->α(编号)

当下的选择未必正确, 但此刻"你别无选择"

还是上面那个例子, 我们来构造它的预测分析表

显然 上面这个文法 不符合 LL(1) 文法

3.4 非递归的预测分析算法

前面我们给出了递归预测分析的伪代码, 我们当然也可以借助栈来实现非递归的预测分析:

龙书上给出了伪代码描述:

值得注意的是, LL(1) 是 left to right, 所以我们压入非终结符号的产生式时要逆序压入, 这样弹栈的时候是顺序弹出的

3.5 文法等价变换

3.5.1 提取公共前缀

公共前缀: A的不同产生式的右部具有相同的前缀, 这种情形不满足自顶向下的语法分析条件.

可用提取左因子的方法消除产生式的公共前缀, 假定关于A的规则是:

A→δB1 | δB2 |…| δBn|γ1|γ2|…|γm(其中每个γ不以δ开头)

则将这些规则写成:

• A -> δA’ | γ1 | γ2 | … | γm
• A’ -> β1 | β2 | … | βn

经过反复提取左因子，就能够使每个非终极符的不同产生式的右部具有不同的前缀.

例如:

A->aB|aC|aD
B->bB|bD|c
D->d

修改:
A->aA'
A'->B|C|D
B->bB'|c
B'->B|D
D->d

3.5.2 消除直接左递归

• 对于简单情形 A->Aα|β 即有 A=>βαα…α
  • 则转化 A->βA’ A’->αA’|ε
• 对于一般情形
  • A->Aα1 | Aα2 | … | Aαm | β1 | β2 | … | βn
  • 则转化为
  • A -> (β1 | β2 | … | βn) A’
  • A’->(α1 | α2 | … | αm)A’ | ε

例子:

E->E+T|T
T->T*F|F
F->(E)|i

修改:
E->TE'
E'->+TE'|ε
T->FT'
T'->*FT'|ε
F->(E)|i

上面两种等价变换 可以将一些不是 LL(1) 文法改造为 LL(1)文法, 但显然有局限. 这种局限来自于LL(1) 本身描述能力就有限.

不展开细嗦了.

3.6 总结

LL(1) 语法分析器

• L: 从左向右(left-to-right)扫描输入
• L: 构建最左(leftmost)推导
• 1: 只需向前看一个输入符号便可确定使用哪条产生式

四、自底向上的语法分析

目前最流行的自底向上的语法分析器都基于所谓的 LR(k) 语法分析的概念，我们这里只讨论 k = 0 和 k = 1 的情况。

我们想要得到一个语法分析器，前面的LL(1) 是通过扫描声明式的规范来得到一张表，通过表驱动的代码来生成语法分析器。

那么LL(1) 有什么优缺点呢？

从 左(L) 向右 读入程序，最**左(L)推导，采用一个(1)**前看符号。

• 优点：
  • 算法运行高效
  • 有现成的工具可用
• 缺点：
  • 能分析的文法类型受限
  • 往往需要文法的改写

4.1 自底向上的语法分析

• 研究其中最重要也是最广泛应用的一类
  • LR分析算法(移进-归约算法)
    • 算法运行高效
    • 有现成的工具可用
    • 相较于LL(1)，有着更强的描述能力，且不需要文法改写
  • 这也是目前应该广泛的一类语法分析器的自动生成器中采用的算法
    • YACC，bison，CUP，C#yacc, 等

基本思想

假如我们有这样的文法：

0: S -> E
1: E -> E + T
2:    | T
3: T -> T * F
4:    | F
5: F -> n

那么对于 表达式 2 + 3 * 4我们是如何自底向上分析的呢？

其实就是 最右推导的逆过程

2 + 3 * 4
F + 3 * 4
T + 3 * 4
E + 3 * 4
E + F * 4
E + T * 4
E + T * F
E + T
E
S

上面的过程很好理解，但是过于理想，我们可能会出现二义性或者错误的规约，我们怎样保证上面的规约过程（归约到开始符号）？

4.2 LR(0) 分析算法

从**左(L)向右读入程序，最右(L)**推导，不用前看符号来决定产生式的选择(0个前看符号)

优点:

• 容易实现

缺点:

• 能分析的文法有限

4.2.1 点记号

为了方便标记语法分析器已经读入了多少输入，我们可以引入一个点记号。

E  +  3  ·  *  4
-------     ----
已经读入     剩余的输入

我们把前面那个示例的自底向上分析加上点记号：

2 · + 3 * 4
F · + 3 * 4
T · + 3 * 4
E · + 3 * 4
E + · 3 * 4
E + 3 · * 4
E + F · * 4
E + T · * 4
E + T * · 4
E + T * 4 ·
E + T * F ·
E + T ·
E ·
S ·

4.2.2 生成逆序的最右推导

上面的过程需要两个步骤：

• 移进 一个记号到栈顶上，或者
• 归约 栈顶上的n个符号(某产生式的右部)到左部的非终结符
  • 对产生式 A -> β1 … βn
    • 如果βn…β1在栈顶上，则弹出 βn…β1
    • 压入 A

核心的问题：如何确定移进和规约的时机

4.2.3 算法思想

LR 语法分析器实际上维护了一些状态，每个状态代表了一个**项目(item)**的集合

项目(item) 是 一个产生式 加上位于它的体中某处的点，例如 产生式 A->XYZ 产生了四个项：

1. A -> · XYZ
2. A -> X · YZ
3. A -> XY · Z
4. A -> XYZ ·

我们还是先看一个例子：

0: S' -> S$
1: S -> x x T
2: T -> y

分析输入串：x x y $

下面这个 DFA 描述了 我们行进的过程

我们怎样利用这个 DFA 来分析输入串”xxy$“呢？

\						·xxy$
1, x, 2					· xy$
1, x, 2, x, 3			 · y$
1, x, 2, x, 3, x, y, 4	  · $
1, x, 2, x, 3, x, T, 5    · $			// 规约
1, S, 6					· $			   // 规约
读入 $ 接受

4.2.4 LR(0) 分析表

根据上面的 DFA 我们可以构造出 这样一张 LR(0) 分析表

这张表描述了 每个状态 在接收不同输入时的动作和转移

4.2.5 表驱动的伪代码

stack = []
push($)			// $：end of file
push(1)			// 1：initial 	state
while (true)
	token t = nextToken()
	state s = stack[top]
	if (ACTION[s, t] == "si")
		push(t); push(i)
	else if (ACTION[s, t] == "rj")
		pop(the right hand of production "j: X -> β")
		state s = stack[top]
		push(X); push(GOTO[s, X])
	else error(...)

4.2.6 LR(0) 分析表构造算法

C0 = closure(s' -> · s$)	// the init closure
SET = {C0}				   // all states
Q = enQueue(C0)			   // a queue
while (Q is not empty)
	C = deQueue(Q)
	foreach (x in (N ∪ T))
		D = goto(C, x)
		if (x in T)
			ACTION[C, x] = D
		else GOTO[C, x] = D
		if (D not in SET)	// 新状态
			SET ∪= {D}
			enQueue(D)

goto (C, x)
	temp = {}	// a set
	foreach (C's item i: A -> β · x γ)
		temp ∪= {A -> β x · γ}
	return closure (temp)

closure (C)
	while (C is still changing)
		foreach (C's item i: A -> β · B γ)
			C ∪ {B -> ...}

这里值得特别解释一下 闭包closure 和 goto

项目集的闭包

如果 I 是文法 G 的一个项目集，那么 CLOSURE(I) 就是根据下面的两个规则从 I 构造得到的项目集：

1. 一开始将 I 加入到 CLOSURE(I) 中
2. 如果 A -> α · B β 在 CLOSURE(I) 中, B -> γ 是一个产生式, 并且 项 B -> ·γ 不在CLOSURE(I)中, 就将这个项加入其中. 不断应用这个规则, 直到没有新项可以加入到 CLOSURE(I) 中为止.

可以结合DFA中的状态1, 3 以及伪代码 来理解

GOTO 函数

GOTO(I, X), 其中 I 是一个 项目, 而 X 是一个 文法符号

GOTO(I, X) 被定义为 I 中所有形如 [A -> α · X β] 的项所对应的项 [A->αX · β] 的集合的闭包

GOTO函数用于定义 一个文法的 LR(0) 自动机中的一个转换, 这个自动机的状态对应于项目集, 而GOTO(I, X) 描述了 输入为 X 时 离开 状态I 的转换

比如 I 是 两个项的集合: [E’ -> E ·], [E -> E · + T]

那么 GOTO(I, +) 为如下内容:

E -> E + · T
T -> · T * F
T -> · F
F -> · (E)
F -> · id

4.3 SLR 分析算法

LR(0) 分析算法的缺点:

• 对每一个形如**X -> α · **的项目
  • ·直接把 α归约成X 紧跟一个“goto’
  • 尽管不会漏掉错误，但会延迟错误发现时机
    • 练习: 尝试"xxyx"
    • 练习发现, 到状态5后还会被规约, 然后读入x后才会报错
• LR(0)分析表中可能包含冲突

问题1: 错误定位

我们看下面这个文法:

0: S' -> S$
1: S -> x S
2: S -> y

不难画出下面这个 自动机:

从而得出 LR(0) 分析表

上面加红的部分代表什么?

状态3遇到x, 如果把 S -> y · 规约为 S, 我们知道 S后面是不能够跟 x 的, 也就是说 表中该项是无效的

同样的, 我们状态5如果 遇到x然后规约, 到达状态4, 我们无法得到$, 也会错误.

对于 java, c 语言等高级语言, 它们的 LR(0)自动机 和 LR(0) 分析表的规模很大, 表项可能几十上百, 因此我们去掉这样的 无效项的收益还是很客观的.

问题2: 冲突

再看这样一个文法:

0: S -> E$
1: E -> T+E
2: E -> T
3: T -> n

我们看状态3 那个 项目集

我们看到 + 后, 可以选择 规约, 也可以选择移进, 我们不能确定哪个正确. 如果做出错误的Action, 还要进行回溯, 带来效率问题

状态3 包含 移进-规约冲突

4.3.1 SLR 分析算法

• 和LR(0) 分析算法基本步骤相同
• 仅区别于对规约的处理
  • 对于状态 i 上的项目 X -> α ·
    • 仅对于 y ∈ FOLLOW(X) 添加 ACTION[i, y]

4.4 LR(1) 分析算法

我们回看 SLR 分析算法的思想

• 基于LR(0)，通过进一步判断一个前看符号来决定是否执行归约动作
  • X -> α · 归约，当且仅当y ∈ FOLLOW(X)
• 优点:
  • 有可能减少需要归约的情况
  • 有可能去除需要移进-归约冲突
• 缺点:
  • 仍然有冲突出现的可能

SLR 分析表中的冲突

看这样一个文法:

L, R 就是 左值和右值

S' -> S$
S -> L = R
S -> R
L -> *R
L -> id
R -> L

可以得到这样一个自动机

状态2又是一个 引进-规约冲突

由于 FOLLOW® 包含 =, 所以我们 遇到 = 时候 可以将 L 规约为 R, 这个时候就会有问题了, 右值没法接 =

4.4.1 LR(1) 项目

• [X -> α · β, α] 的含义是:
  • α 在栈上
  • 剩余的输入能够匹配 βα
• 当规约 X -> αβ时, a 是前看符号
  • 把 ‘reduce by X -> αβ’ 填入ACTION[s, a]

4.4.2 LR(1) 项目的构造

• 其他和LR(0)相同, 仅闭包的计算不同
  • 对项目**[X -> α · γ β, a]**
    • 添加 [Y -> · γ, b]
      • 其中 b ∈ FIRST_S(βa)

4.4.3 LR(1) 项目集

还是这个文法:

S' -> S$
S -> L = R
S -> R
L -> *R
L -> id
R -> L

根据新的 闭包的求法, 我们可以得到下面这个自动机

4.5 LALR 分析算法

• 把类似的项目集进行合并
• 需要修改ACTION表和GOTO表, 以反映合并的效果

4.6 对二义性文法的处理

• 二义性文法无法使用LR分析算法分析
• 不过，有几类二义性文法很容易理解，因此，在LR分析器的生成工具中，可以对它们特殊处理
  • 优先级
  • 结合性
  • 悬空else

这里值得说明的是，antlr-v4 并没有采用LR 语法分析，而是采用了LL(*) 算法（也被称为 all-star）