知识

语法分析（解析）

  • 解析概述：

    • 职能与责任

  • 上下文无关语法

    • 概念和术语

  • 编写和设计语法

  • 解决语法问题/困难

  • 自顶向下解析

    • 递归下降与预测下降

  • 自底向上解析

    • LR和LALR

  • 结束语/展望未来

有哪些典型错误？
#include<stdio.h>

int f1(int v){ 
  	int i,j=0;
	for (i=1;i<5;i++){
     	j=v+f2(i) //VC++MS报道：“f2”未定义；假设extern返回int
		//语法错误：缺少“；”在“}”之前
    }
	return j; 
}
int f2(int u){ 
  	int j;
	j=u+f1(u*u);
	return j; 
}
int main(){ 
  	int i,j=0;
	for (i=1;i<10;i++){ 
      	j=j+i*i//语法错误：缺少“；”在标识符“printf”之前 
        printf(“%d\n”,i); 
    }
	printf("%d\n",f1(j));
	return 0;
}
解析器（续）

  • 我们将解析器分为两组：

    1. 自上而下解析器(自顶向下)

      • 从根开始，从上到下创建解析树。

    2. 自底向上解析器(自底向上)

      • 从下到上创建解析树；从树叶开始

  • 自上而下和自下而上的解析器都从左到右扫描输入（一次一个符号）。

  • 高效的自顶向下和自下而上解析器只能对上下文无关语法的子类实现。

    • LL用于自顶向下分析

    • LR用于自底向上解析

编译期间的解析
  • 解析器处理单词流。
  • 最小的物品是单词。 alt
错误处理
  • 检测错误
  • 寻找它们出现的位置
  • 清晰/准确的陈述
  • 恢复（传递）以继续并查找以后的错误
  • 不要影响“正确”程序的编译
错误恢复策略（第164页）

恐慌模式–丢弃单词，直到找到“同步”单词（结束“；”，“}”等）

  • 设计师的决定
  • 问题： 跳过输入→未完成声明–导致更多错误→跳过材料中的遗漏错误
  • 优点：易于理解的→适用于每个语句1个错误

短语级别–输入时的局部更正

  • “,” →”;” – 删除“，”–插入”

  • 也是设计师的决定

  • 不适合所有情况

  • 与紧急模式结合使用，允许跳过较少的输入

  • 错误产品：

    • 用规则扩充语法

    • 用于构造/生成解析器的扩充语法

    • 示例：为C赋值语句中的：=添加规则 报告错误，但继续编译

    • 自我纠正+诊断信息

  • 全球修正：

    • 添加/删除/替换符号是很有可能的——可能会做很多改变！

    • 可用于最小化更改的算法代价高昂-关键问题

语法分析器

  • 语法分析器创建给定源程序的语法结构。

  • 这种语法结构主要是一个解析树。

  • 语法分析器也称为解析器。

  • 编程的语法由上下文无关语法（CFG）描述(上下文无关文法）. 我们将在CFG的描述中使用BNF（巴克斯-诺尔形式）符号。

  • 语法分析器（解析器）检查给定的源程序是否满足上下文无关语法隐含的规则。

    • 如果满足，解析器将创建该程序的解析树。

    • 否则，解析器会给出错误消息。

  • 上下文无关语法

    • 给出编程语言的精确语法说明。

    • 语法设计是编译器设计的初始阶段。

    • 语法可以通过一些工具直接转换成解析器。

语法>>语言

为什么正式描述语言的语法很重要？

  1. 精确、易于理解的表述

  2. 编译器编写工具可以获取语法并生成编译器（YACC、BISON）

  3. 允许语言进化（新语句、语句更改等）。语言不是静态的，而是不断升级以添加新功能或修复“旧”功能

ADA → ADA9x, C++ Adds: Templates, exceptions,

语法与解析过程有什么关系？

RE与CFG（第172页）

  • 正则表达式

    • 词汇分析的基础

    • 表示常规语言

  • 上下文无关语法

    • 解析的基础

    • 表示语言结构

    • 描述上下文无关语言 alt

上下文无关语法

  • 编程语言固有的递归结构由上下文无关语法定义。

  • 在上下文无关语法中，我们有：

    • 一组有限的终端(终结符）（在我们的例子中，这将是一组令牌）

    • 一组有限的非终端(非终结符）（语法变量）

    • 一组有限的生产规则(产生式） 以下面的形式： A→ α，其中A是非终端，α是终端和非终端串（包括空串）

    • 开始符号（非结束符号之一）

  • 例子：

E → E + E | E – E | E * E | E / E | - E
E → ( E )
E → id 
E → num
概念和术语

定义：上下文无关语法（CFG）由T、NT、S、PR描述，其中：

T：语言的终端/标记

NT：非终结符，表示语法生成的字符串集&在语言中

S:开始符号，S∈NT，它定义了语言的所有字符串

PR：表示如何组合T和NT以生成语言的有效字符串的产生式规则。

PR:NT→ （T|NT）*

与正则表达式/DFA/NFA一样，上下文无关语法也是一个数学模型

范例语法

为了简化/标准化符号，我们提供了术语概要。 alt

术语（续）
  • L（G）是G（由G生成的语言）的语言，G是一组句子。
  • 一句话(句子）L（G）是G的一系列终端符号。
  • 如果S是G的起始符号，那么ω是L（G）的一个句子如果S→+ ω，其中ω是G的一串终端。
  • 可以由语法生成的语言被称为上下文无关语言。
  • 如果G是上下文无关语法，那么L（G）是上下文无关语言。
  • 如果两个语法产生相同的语言，那么它们是等价的。

s→* α

  • 如果α包含非终结符，则称为G的一种句子形式。

  • 如果α不包含非末端，则称为G的句子。

例如 E → E + E→ id + E→ id + id

这与语言有什么关系？

alt

示例语法-术语

alt

派生词

这里的中心思想是，产品被视为重写规则(重写规则）

其中，左侧的非端子被生产线右侧的字符串替换。

E→ E+E

  • E+E源于E

    • 我们可以用E+E替换E

    • 要做到这一点，我们必须有一个生产规则E→我们语法中的E+E。

E→ E+E→ id+E→ id+id

  • 非终端符号的替换序列称为派生(推导）来自E的id+id。

  • 一般来说，推导步骤是alt

语法概念

派生中的一个步骤是用产生式规则的RHS替换NT的零个或一个操作。 alt

其他派生概念

示例4.4（参考示例（4.3））

E → -E → -(E) → -(E+E) → -(id+E) → -(id+id)

或

E → -E → -(E) → -(E+E) → -(E+id) → -(id+id)

  • 在每一个派生步骤中，我们可以选择G的句子形式中的任何一个非终结符来替换。

  • 如果我们总是在每个派生步骤中选择最左边的非终端，那么这个派生称为最左边的派生(最左推导）.

  • 如果我们总是在每个派生步骤中选择最右边的非终结符，那么这个派生称为最右边的派生(最右推导）.

派生示例

派生：解析输入的操作可以在解析树中用图形表示

最左侧：替换最左侧的非端子符号 alt 最右边：替换最左边的非端子符号 alt alt

最左和最右派生

alt

  • 我们将看到自上而下的解析器试图找到给定源程序最左边的派生。

  • 我们将看到，自下而上的解析器试图以相反的顺序找到给定源程序最正确的派生。

课堂派生练习1

alt alt

解析树

  • 解析树的内部节点是非终端符号。

  • 解析树的叶子是终端符号。

解析树可以看作是派生的图形表示。

从派生构建解析树

alt

LM/RM派生的示例

E→ E op E |（E）|-E | id

op→ + | - | * | / | ↑

最左边的派生词：id+id*id

最右边的派生词：id+id*id

alt