1.形式语言基础

1.1文法的定义

PASCAL语言语法例子：

1.2上下文无关文法

高级语言语法的表示形式有两种：

但是这里主要介绍上下文无关文法。

例子：

1.3基本概念

直接推导相当于用规则右部的串代替了规则左部的串，也称作是我们使用了一次规则进行替换。

简单短语的获取和推导的顺序无关

1.4文法分类

对“文法”一词如无特殊说明则均指上下文无关文法（2型文法）。

文法G所描述的语言是由文法的开始符推出的所有终极符号串的集合。

2.语法树

2.1语法树的定义

例子：

语法树和语法概念的关系：

例子：

2.2语法树的作用

• 语法树反映出我们推导的过程，每一步节点的生长过程都可以对应到我们的一步推导。

• 语法树反应出串的语法结构。

3.语法

3.1语法的二义性

对一个文法G，如果至少存在一个句子，有两棵（或两棵以上）不同的语法树，则称该句子是二义性的，包含有二义性句子的文法称为二义性文法，否则，该文法是无二义性的。

因为左结合和优先级高这两个原则的优先级没有限制。

3.2消除二义性

3.2.1方法一：文法变换

3.2.2方法二：添加语义规则

3.3语法二义性的判定和利用

目前，不存在一个一般性的方法来判断一个现有文法是否为二义性文法。

如果文法G是无二义性的，则它的任何句子alpha的最左推导和最右推导对应的语法树必定相同。

3.4语法等价变化

3.4.1提取公共前缀

例子：

3.4.2消除直接左递归

下面这个公式很重要：

例子：

整个文法出题的例子：

example 1：

example 2：

example 3：

4.语法分析

功能：分析单词串是如何构成语句的；分析语句是如何构成程序的；分析程序的结构。

4.1自顶向下语法分析概述

非确定的自顶向下语法分析方法：

4.2相关前置概念

下面介绍三个集合

4.2.1三个集合的定义

• First集

  • 

• Follow集

  • 

• Predict集

  • 

4.2.2三个集合的计算

First集

例子：

Follow集

（#表示处理串的结束标志，有的书上也用美元号，表示结束的标示）

例子：

Predict集

例子：

类型题：

4.3确定的自顶向下的语法分析方法

4.3.1 LL（1）文法

定义：

动作：

分析动作例子：

• 成功：

• 失败：

LL（1）分析表

LL（1）分析器组成：

分析表定义：

构造方法：

完整分析例子：

4.3.2 递归下降法

判断：和LL1一样

原理：

参考资料：

吉林大学编译原理PPT（刘宇舟）

【编译原理】4—语法分析Syntax Analysis——自顶向下（LL(1)文法表驱动判断）_ll1 表驱动-CSDN博客