语法分析

语法分析

图片

图片

图片

图片

  • 数学理论：上下文无关文法（CFG）
    • 描述语言语法规则的数学工具
  • 自顶向下分析
    • 递归下降分析算法（预测分析算法）
    • LL分析算法
  • 自底向上分析
    • LR分析算法

上下文无关文法

图片

  • 自然语言中的句子的典型结构：
    • 主语 谓语 宾语
    • 名字动词名词
  • 例子：
    • 名词：{羊、老虎、草、水}
    • 动词：{吃、喝}

图片

定义

  • 上下文无关文法 G 是一个四元组：G = (T, N, P, S)
    • 其中 T 是终结符集合
    • N 是非终结符集合
    • P 是一组产生式规则
      • 每条规则的形式：X -> β1 β2 ...βn
        • 其中 X ∈ N, βi ∈ (T ∪ N)
    • S 是唯一的开始符号（非终结符）
      • S ∈ N

图片

图片

推导

  • 给定文法 G，从 G 的开始符号 S 开始，用产生式的右部替换左侧的非终结符
  • 此过程不断重复，直到不出现非终结符为止
  • 最终的串称为句子

最左推导和最右推导

  • 最左推导：每次总是选择最左侧的符号进行替换
  • 最右推导：每次总是选择最右侧的符号进行替换

语法分析的任务

给定文法 G 和句子 s ，语法分析要回答的问题：是否存在对句子s的推导？

图片

分析树与二义性

分析树

  • 推导可以表达成树状结构
    • 和推导所用的顺序无关（最左、最右、其他）
  • 特点:
    • 树中的每个内部节点代表非终结符
    • 每个叶子节点代表终结符
    • 每一步推导代表如何从双亲节点生成它的直接孩子节点

图片

图片

二义性文法

  • 给定文法 G，如果存在句子 s，它有两棵不同的分析树，那么称G是二义性文法
  • 从编译器角度，二义性文法存在问题：
    • 同一个程序会有不同的含义
    • 因此程序运行的结果不是唯一的
  • 解决方案：文法的重写

图片

左递归的文法实现的句子具有左结合性；右递归文法实现的句子具有右结合性

自顶向下分析

  • 语法分析：给定文法 G 和句子 s，回答 s 是否能够从 G 推导出来？
  • 基本算法思想：从 G 的开始符号出发，随意推导出某个句子 t，比较 t 和 s
    • 若 t == s，则回答“是”
    • 若 t != s，则?
  • 因为这是从开始符号出发推出句子，因此称为自顶向下分析
    • 对应于分析树自顶向下的构造顺序

代码

tokens[]; // all tokens
i = 0;
stack = [S];  // S 为开始符号
while (stack != [])
  if (stack[top] is a terminal t)
    if (t == tokens[i++])
      pop();
    else
      backtrack();
  else if (stack[top] is a nonterminal T)
    pop();  push(the next right hand side of T);

算法的讨论

  • 算法需要用到回溯
    • 给分析效率带来问题
  • 而就这部分而言（就所有部分），编译器必须高效
    • 编译上千万行的内核等程序
  • 因此，实际上我们需要线性时间的算法
    • 避免回溯
    • 引出递归下降分析算法和LL(1)分析算法

用前看符号避免回溯

递归下降分析

  • 也称为预测分析
    • 分析高效（线性时间）
    • 容易实现（方便手工编码）
    • 错误定位和诊断信息准确
    • 被很多开源和商业的编译器所采用
      • GCC 4.0，LLVM，...
  • 算法基本思想：
    • 每个非终结符构造一个分析函数
    • 用前看符号指导产生式规则的选择

算法

图片

parse_S() {
  parse_N();
  parse_V();
  parse_N();
}

parse_N() {
  token = tokens[i++];
  if (token == s || token == t || token == g || token == w) {
    return;
  }
  error("...");
}

parse_V() {
  token = tokens[i++];
  if (token == e || token == d) {
    return;
  }
  error("...");
}

一般的代码框架

图片

parse_X() {
  token = nextToken();
  switch (token) {
    case ...: // β11 ... β1i
    case ...: // β21 ... β2i
    case ...: // β31 ... β3i
    ...
    default:  error("...");
  }
}

对算术表达式的递归下降分析

图片

a first try

parse_E() {
  token = tokens[i++];
  if (token == num) {
    ? // E + T or T
  } else {
    error("...");
  }
}

选择不当将有可能再次引起回溯

a second try

图片

parse_E() {
  parse_T();
  token = tokens[i++];
  while (token == +) {
    parse_T();
    token = tokens[i++];
  }
}

parse_T() {
  parse_F();
  token = tokens[i++];
  while (token == *) {
    parse_F();
    token = tokens[i++];
  }
}

LL(1) 分析算法

  • 从左（L）向右读入程序，最左（L）推导，采用一个（1）前看符号
    • 分析高效（线性时间）
    • 错误定位和诊断信息准确
    • 有很多开源或商业的生成工具
      • ANTLR，...
  • 算法基本思想：
    • 表驱动的分析算法

图片

图片

FIRST 集合

图片

不动点算法

foreach (nonterminal N) {
  FIRST(N) = {};
}

while (sime set is changing) {
  foreach (production p: N -> β1 ... βn) {
    if (β1 == a...) {
      FIRST(N) ∪= {a};
    }
    if (β1 == M...) {
      FIRST(N) ∪= FIRST(M);
    }
  }
}

把 FIRST 集合推广到任意串上

图片

图片

图片

构造 LL(1) 分析表

图片

分析表中的冲突

图片

分析表的构造

  • 首先研究右侧的例子：
    • FIRST_S(X Y Z)?
      • 一般情况下需要知道某个非终结符是否可以推出空串
      • NULLABLE
    • 并且一般需要知道在某个非终结符后面跟着什么符号
      • 跟随集FOLLOW

图片

NULLABLE 集合

  • 归纳定义：
    • 非终结符 X 属于集合 NULLABLE，当且仅当：
      • 基本情况：
        • X ->
      • 归纳情况:
        • X -> Y1 ..., Yn
          • Y1, ..., Yn 是n个非终结符，且都属于NULLABLE集
NULLABLE = {};

while (NULLABLE is still changing) {
  foreach (production p: x -> β) {
    if (β == ε) {
      NULLABLE ∪= {X};
    }
    if (β == Y1 ... Yn) {
      if (Y1 ∈ NULLABLE && ... && Yn ∈ NULLABLE) {
        NULLABLE ∪= {X};
      }
    }
  }
}

FIRST 集合计算公式

  • 基于归纳的计算规则：
    • 基本情况：
      • X -> a
        • FIRST (X) ∪= {a}
    • 归纳情况：
      • X -> Y1 Y2 ... Yn
        • FIRST (X) ∪= FIRST(Y1)
        • if Y1 ∈ NULLABLE, FIRST (X) ∪= FIRST(Y2)
        • if Y1,Y2 ∈ NULLABLE, FIRST(X) ∪= FIRST(Y3)
        • ...

不动点算法

foreach (nonterminal N) {
  FIRST(N) = {};
}

while (some set is changing) {
  foreach (production p: N -> β1 ... βn) {
    foreach (βi from β1 upto βn) {
      if (βi == a...) {
        FIRST(N) ∪= {a};
        break;
      }
      if (βi == M...) {
        FIRST(N) ∪= FIRST(M);
        if (M is not in NULLABLE) {
          break;
        }
      }
    }
  }
}

FOLLOW 集的不动点算法

foreach (nonterminal N) {
  FOLLOW(N) = {};
}

while (some set is changing) {
  foreach (production p: N -> β1 ... βn) {
    temp = FOLLOW(N);
    foreach (βi from βn downto β1) {  // 逆序
      if (βi == a...) {
        temp = {a};
      }
      if (βi == M...) {
        FOLLOW(M) ∪= temp;
        if (M is not NULLABLE) {
          temp = FIRST(M);
        }
        else {
          temp ∪= FIRST(M);
        }
      }
    }
  }
}

计算 FIRST_S 集合

foreach (prodcution p) {
  FIRST_S(p) = {};
}

calculate_FIRST_S (production p: N1 -> β1 ... βn) {
  foreach (βi from β1 to βn) {
    if (βi == a...) {
      FIRST_S(p) ∪= {a};
      return;
    }
    if (βi == M...) {
      FIRST_S(p) ∪= FIRST(M);
      if (M is not NULLABLE) {
        return;
      }
    }
  }
  FIRST_S(p) ∪= FOLLOW(N);
}

图片

LL(1) 分析表

图片

LL(1) 分析器

tokens[]; // all tokens
i = 0;
stack = [S];  // S 开始符号
while (stack != []) {
  if (stack[top] is a terminal t) {
    if (t == tokens[i++]) {
      pop();
    } else {
      error(...);
    }
  } else if (stack[top] is a nonterminal T) {
      pop();
      push(table[T, tokens[i]]);
  }
}

LL(1) 分析冲突处理

图片

图片

消除左递归

图片

图片

图片

提取公因子

图片

LR(0) 分析算法

LL(1) 分析

  • 从左（L）向右读入程序，最左（L）推导，采用一个（1）前看符号
    • 优点：
      • 算法运行高效
      • 有现成的工具可用
    • 缺点：
      • 能分析的文法类型受限
      • 往往需要文法的改写

自底向上分析算法

  • 研究其中最重要也是最广泛应用的一类
    • LR分析算法（移进-归约算法）
      • 算法运行高效
      • 有现成的工具可用
    • 这也是目前应该广泛的一类语法分析器的自动生成器中采用的算法
      • YACC, bison, CUP, C#yacc, 等

基本思想

图片

点记号

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

图片

自底向上分析

图片

另外的写法

图片

生成一个逆序的最右推导

  • 需要两个步骤：
    • 移进一个记号到栈顶上，或者
    • 归约 栈顶上的n个符号（某产生式的右部）到左部的非终结符
      • 对产生式 A -> β1 ... βn
        • 如果 βn ... β1 在栈顶上，则弹出 βn... β1
        • 压入A
  • 核心的问题：如何确定移进和归约的时机？

算法思想

图片

LR(0) 分析表

图片

LR(0) 分析算法

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(...);
}

LR(0) 分析表构造算法

C0 = closure(S' -> ·S$);  // the init closure
SET = {C0};
Q = enQueue(C0);
while (Q is not empty) {
  C = deQueue(Q);
  foreach (x ∈ (N ∪ T)) {
    D = goto(C, x);
    if (x ∈ T) {
      ACTION[C, x] = D;
    } else {
      GOTO[C, x] = D;
    }
    if (D not ∈ SET) {
      SET ∪= {D};
      enQueue(D);
    }
  }
}

goto(C, x) {
  temp = {};
  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 -> ...};
    }
  }
}

SLR 分析算法

图片

LR(0) 分析算法

  • 从左（L）向右读入程序，最右（L）推导，不用前看符号来决定产生式的选择（0个前看符号）
    • 优点：
      • 容易实现
      • 缺点：
        • 能分析的文法有限

LR(0) 分析算法的缺点

  • 对每一个形如 X -> α· 的项目
    • 直接把 α 归约成 X, 紧跟一个“goto”
    • 尽管不会漏掉错误，但会延迟错误发现时机
  • LR(0)分析表中可能包含冲突

图片

图片

SLR 分析算法

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

图片

图片

LR(1) 分析算法

SLR 分析算法的思想

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

图片

LR(1) 的项目

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

LR(1) 项目的构造

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

图片

图片

LALR 分析算法

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

对二义性文法的处理

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

图片

LR(1) 分析工具

语法分析器的实现方法

  • 手工方式
    • 递归下降分析器
  • 使用语法分析器的自动生成器
    • LL(1), LR(1)
  • 两种方式在实际的编译器中都有广泛的应用
    • 自动的方式更适合快速对系统进行原型

历史发展

  • YACC 是 Yet Another Compiler-Compiler 缩写
  • 在1975年首先由Steve Johnson在Unix上实现
  • 后来，很多工具在此基础上做了改进：
    • 例如 GNU Bison
    • 并且移植到了很多其他语言上
  • YACC 现在是一个标准的工具（见IEEE Posix 标准P1003.2）

Yacc

用户代码和Yacc声明：可以在接来的部分使用

%%

语法规则：上下文无关文法的规则及相应语义动作

%%

用户代码：用户提供的代码

首先在 Linux/Ubuntu 上使用 sudo apt install bison -y 安装 bison

创建一个 .y 文件：

%{
#include <stdio.h>
#include <stdlib.h>
int yylex();
void yyerror();
%}

%left '+'

%%

lines: line
     | line lines
;

line: exp'
';

exp: n
   | exp '+' exp
;

n: '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' | '0';

%%

int yylex()
{
        return getchar();
}

void yyerror(char *s)
{
        fprintf(stderr, "%s
", s);
        return;
}

int main(int argc, char ** argv)
{
        yyparse();
        return 0;
}

图片

使用 bison text.y 将其编译成 test.tab.c 文件：

图片

然后使用 gcc test.tab.c 将生成分析后的文件编译，得到可执行文件：

图片

执行 ./a.out 即可进行语法分析：

图片

不一定每天 code well 但要每天 live well
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/geekfx/p/13747109.html