编译原理备忘录-语法分析与词法分析

2019-11-01

1. 文法

2. 相关概念

规则（产生式）：形如$a\rightarrow b$ ,$a::=b$，a为产生式左部，b为右部
- 候选式：${b_i|a\rightarrow b_i }$
文法G：四元组$(V_N,V_T,P,S)$:
- $V_N$:非终结符，一般用大写字符标识（A,B）
- $V_T$:终结符，一般用小写字符（a,b,c）
- $P$:规则
- $S$:识别符/开始符
推导：
- 直接推导==归约。eg: a->b是文法G的规则，有m,n属于字符集，存在v=man w=mbn，则说w是v的直接推导，w归约到v。$v\Rightarrow w$
- $v{\Rightarrow}^{+}w$： $v\Rightarrow w_1 \Rightarrow w_2…\Rightarrow w_n$
- $v{\Rightarrow}^{*}w$：$v{\Rightarrow}^{+}w$或$v=w$
- 句型：文法G，有x是从识别符开始推导得到，即$S\Rightarrow^{+}x$，则x是G的句型，若x仅由终结符组成，则x称为句子
  - 一句话：只由终结符组成的句型称为句子
- 语言：${x|S=>x,x{\in}V_T}$
空串
ε是指某个包含非终结符号的文法符号串的推导为空，例如A->ε。咋看上去和空集好像差不多，其实它们却有本质的区别：空集是面向结果的，即一个文法所有可能推导的最终语句；而ε则是面向定义的，即某个非终结符号可以推导为空，这样的定义可以在推导过程重复使用。

2.1. 叶子结点——短语、句柄与集族

> 短语、简单短语都是**针对某一句型**的，是**相对于某个非终结符号**的，并且**任何句型本身一定是相对于识别符号Z的短语。** > > 句柄**：任一句型的最左简单短语称为该句型的句柄，一个句型只有一个句柄。**

- 短语: $T * F$, $E+T * F$ - 直接短语（简单短语）：$T * F$ - 句柄：$T * F$

对于子树$T$来说，其所有叶子节点为：$T * F$，对于$E$来说，其所有叶子节点为:$E+T *F$故短语为$T * F$和 $E+T * F$

集族

集族是一种特殊的集合，以集合为元素的集合称为集族。例如，集A的幂集P(A)是一个集族，P(P(A))，P(P(P(A))都是集族。又例如，由空集φ、集合A={1，2，3}作为元素的集合M={φ，A}是一个集族。

3. 文法类型

0型：对G的每一个产生式a->b，有$a{\in}(V_N{\bigcup}V_T)^{}$（闭包）且至少包含一个非终结符，$b{\in}(V_N{\bigcup}V_T)^{}$
1型：~，皆有$|b|{\geq}|a|$，仅仅$S\rightarrow e$除外（此之谓空产生式）。又称上下文有关的（content-sensitive）
- $|x|$：$x$的长度。$|e|=0$
- 意即：当$a$满足某一特定条件时，才能被$b$取代
2型：~，皆有a是一个非终结符，且$b{\in}(V_N{\bigcup}V_T)^{*}$。又称上下文无关文法（content-free grammar，CFG）
3型：每一个产生式形式皆是：A->aB，或A->a，A,B都是非终结符，$a{\in}V_T^{*}$。称为正规文法（regular grammar）
例如，以空格为单词划分的英语语句(e.g I am a cat).
Such loop is a typical approach for parsing sentences of a regular language (known as a type 3 language.) Writing such program with CTTL is simple: there is no need to prototype custom Finite State Machine (FSM) for the input language scanner; proper FSM is compiled directly from components of the CTTL expression.
By contrast, an infix notation, used in conventional arithmetic expressions such as “(a+b)*c”, cannot be described by a regular grammar. An arithmetic expression requires a context-free grammar to identify its rules, and is usually defined by a set of BNF, or EBNF productions. If CTTL program needs to parse a context-free language, it invokes a function, designated to be the starting rule of the language. Furthermore, the parser employs a set of semantic actions to collect and process the data.

4. 语法树

语法树（推导树）：对文法G
- 每个结点都是一个标记，此标记是V的一个符号
- 根标记是S
- 若一个结点n至少有一个它自己以外的子孙，并有标记A，则A其必在$V_N$中
- 结点n的直接子孙是$n_1,n_2…n_k$，则$A->A_1A_2…A_k$是P的一个产生式
最左推导：在推导的任何一步$a\Rightarrow b$，都是对$a$的最左非终结符进行替换
最右推导：也叫规范推导
- 由规范推导所得的句型称为规范句型

文法二义：一个文法存在某个句子对应两棵不同的语法树

    E                           E
  / | \                       / | \
  E +  E                     E  *  E
/ | \  |                     |   / | \
E *  E i                     i  E  +  E
|    |                          |     |
i    i                          i     i

4.1. 语法树与分析树

抽象语法树（语法树、推导树）
抽象语法树（Abstract Syntax Tree，AST），或简称语法树（Syntax tree），是源代码语法结构的一种抽象表示。它以树状的形式表现编程语言的语法结构，树上的每个节点都表示源代码中的一种结构。之所以说语法是“抽象”的，是因为这里的语法并不会表示出真实语法中出现的每个细节。比如，嵌套括号被隐含在树的结构中，并没有以节点的形式呈现；而类似于 if-condition-then 这样的条件跳转语句，可以使用带有两个分支的节点来表示
具体语法树（分析树）
A parse tree or parsing tree[1] or derivation tree or concrete syntax tree is an ordered, rooted tree that represents the syntactic structure of a string according to some context-free grammar.
一般的，在源代码的翻译和编译过程中，语法分析器创建出分析树，然后从分析树生成AST

抽象语法树AST

具体语法树

5. 句型分析

定义

当给定一个符号串时，试图按照某文法的规则，构造语法树，以此识别出它是该文法的一个句型
当符号串全是终结符时，就能识别出它是不是某文法的句子

输入输出

输入：由单词组成的字符串

分析方法

自顶向下
- 从根S出发，叶子从左往右匹配输入串符号
自底向上
- 从输入串出发，寻找与某一产生式最右端相等的子串

6. 自顶向下

目标

解决推导过程中如何确定的选择候选式的问题

原理

从输入符号串入手，通过反复查找当前句型的句柄（最左简单短语），并使用文法的产生式把句柄归约成相应的非终极符来一步步地进行分析的。最终把输入串归约成文法的开始符号，表明分析成功

LL分析器是一种处理某些上下文无关文法的自顶向下分析器。因为它从左（Left）到右处理输入，再对句型执行最左推导出语法树（Left derivation，相对于LR分析器）。能以此方法分析的文法称为LL 文法。

LL分析与LL分析表没有必然关系，关键是唯一地决定推导顺序。即如果当前能够做到直接的最左推导，就无需构建LL表

参考：

7. 自底向上

目标

就是要找出当前句型的句柄（或是它的变型），然后根据产生式判别将它归约成什么样的非终极符号

移进-归约法

对输入符号串自左向右地扫描，并将输入符号逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄或其他可归约串就进行归约，归约的结果是将句柄或其他可归约串从栈顶部分弹出，而其相对应的非终结符压入栈中。重复过程直到栈中只剩文法的开始符

原理

从输入符号串入手，通过反复查找当前句型的句柄（最左简单短语），并使用文法的产生式把句柄归约成相应的非终极符来一步步地进行分析的。最终把输入串归约成文法的开始符号，表明分析成功

内容

优先关系矩阵
- 再语法树中越底层，大小越大，取最值
简单优先文法
- 简单优先文法分析算法的主要思想是就是找出当前句型的并归约之。

参考：

课件

8. LR分析

与前面的关系

LR分析法给出一种能根据当前分析栈中的符号串和向右顺序查看输入串的$k$个符号就可唯一确定句柄
LR分析是规范推导的逆过程，故称规范规约过程
相比自顶向下LL(k)和自底向上优先分析方法，LR分析法对文法的限制要少得多

参考：

课件

9. 词法分析

与语法分析关系

$语法\Rightarrow^{请求:下一个单词} 词法$
$词法\Rightarrow^{返回:下一个单词} 语法$

单词分类

关键字：又称保留字
标识符：包括常量名、变量名、过程名等
常数
运算符
界符：如逗号、分号、括号等

正规文法与正规式（正则表达式）与有限自动机（FSM）

$正规文法\Leftrightarrow 正则式$：$S\rightarrow aA|a…\Leftrightarrow S=a(a|d)^{ * }$
$正规文法\Leftrightarrow 有穷自动机$：$S\rightarrow aA|a…\Leftrightarrow 五元组$

单词（Token）

A lexical token or simply token is a string with an assigned and thus identified meaning. It is structured as a pair consisting of a token name and an optional token value. e.g👇
Token name Sample token values
identifier x, color, UP
keyword if, while, return
separator }, (, ;
operator +, <, =
literal true, 6.02e23, "music"
Consider this expression in the C programming language:
x = a + b * 2;
The lexical analysis of this expression yields the following sequence of tokens:
[(identifier, x), (operator, =), (identifier, a), (operator, +), (identifier, b), (operator, *), (literal, 2), (separator, ;)]