语法分析：编译器自上而下和自下而上解析类型

什么是语法分析？

语法分析 是编译器设计过程的第二阶段，其中检查给定的输入字符串以确认形式语法的规则和结构。它分析语法结构并检查给定的输入是否符合编程语言的正确语法。

编译器设计过程中的语法分析是在词法分析阶段之后进行的。它也被称为解析树或语法树。解析树是在语言的预定义语法的帮助下开发的。语法分析器还检查给定的程序是否满足上下文无关语法所暗示的规则。如果满足，解析器将创建该源程序的解析树。否则，它将显示错误消息。

为什么需要语法分析器？

检查代码的语法是否有效
语法分析器可帮助你将规则应用于代码
帮助您确保每个左括号都有相应的右括号
每个声明都有一个类型，并且该类型必须存在

重要的语法分析器术语

语法分析过程中使用的重要术语：

句子： 句子是某个字母上的一组字符。

词素： 词素是语言的最低级句法单位（例如，total、start）。

标记： 标记只是词素的一个类别。

关键字和保留字 – 它是一个标识符，用作语句语法的固定部分。它是一个保留字，不能用作变量名或标识符。

噪音词 – 噪声词是可选的，插入到语句中以增强句子的可读性。

留言 – 这是文档中非常重要的一部分。它主要以 /* */ 或//Blank（空格）显示

定界符 – 它是一个句法元素，标记某个句法单元的开始或结束。例如语句或表达式、“begin”…“end”或 {}。

字符集 – ASCII、Unicode

标识符 – 这是对长度的限制，有助于降低句子的可读性。

Operator 符号 – + 和 – 执行两个基本算术运算。
语言的句法元素

为什么我们需要解析？

解析还会检查输入的字符串是否格式正确，如果不正确，则拒绝它。

以下是编译器设计中解析器执行的重要任务：

帮助您检测所有类型的语法错误
查找发生错误的位置
清晰且准确的错误描述。
从错误中恢复以继续并在代码中查找更多错误。
不应影响“正确”程序的编译。
解析必须通过报告语法错误来拒绝无效文本

解析技术

解析技术分为两类：

自上而下的解析，
自底向上解析

自顶向下解析

在自上而下的解析中，解析树的构造从根开始，然后向叶子进行。

自上而下的解析有两种类型：

预测解析：

预测解析可以预测应该使用哪个产生式来替换特定的输入字符串。预测解析器使用前瞻点，指向下一个输入符号。这种解析技术不存在回溯问题。它被称为 LL(1) 解析器

递归下降解析：

这种解析技术以递归方式解析输入以生成语法树。它由几个小函数组成，每个函数对应语法中的每个非终结符。

自底向上解析

在编译器设计中的自下而上的解析中，解析树的构造从叶开始，然后向根方向处理。它也被称为移位归约解析。编译器设计中的这种解析类型是借助一些软件工具.

错误 – 恢复方法

系统软件解析中常见的错误

词法：错误输入的标识符的名称
句法：括号不匹配或缺少分号
语义：不兼容的值分配
合乎逻辑：无限循环且无法访问代码

解析器应该能够检测并报告程序中发现的任何错误。因此，每当发生错误时，解析器都应该能够处理它并继续解析剩余的输入。程序在编译过程的各个阶段可能会出现以下类型的错误。解析器中可以实现五种常见的错误恢复方法

语句模式恢复

当解析器遇到错误时，它可以帮助您采取纠正措施。这允许其余输入和状态提前解析。
例如，添加缺失的分号是语句模式恢复方法。但是，解析设计人员在进行这些更改时需要小心，因为一次错误的更正可能会导致无限循环。

紧急模式恢复

当解析器遇到错误时，此模式将忽略语句的其余部分，并且不处理从错误输入到分隔符（如分号）的输入。这是一种简单的错误恢复方法。
在这种恢复方法中，解析器逐个拒绝输入符号，直到找到单个指定的同步标记组。同步标记通常使用或之类的分隔符。

短语级恢复

编译器通过插入或删除标记来纠正程序。这允许它从原来的位置继续解析。它对剩余的输入执行纠正。它可以用一些字符串替换剩余输入的前缀，这有助于解析器继续该过程。

错误制作

错误生成恢复会扩展生成错误结构的语言的语法。然后，解析器会针对该结构执行错误诊断。

全局校正

编译器在处理错误输入的字符串时，应该尽可能少地进行更改。给定错误输入的字符串 a 和语法 c，算法将搜索相关字符串 b 的解析树。例如，将 an 转换为 b 所需的一些 token 插入、删除和修改尽可能少。

英语文法

语法是描述语言的一组结构规则。语法为任何句子分配结构。这个术语也指对这些规则的研究，该文件包括形态学、音系学和句法学。它能够描述许多语法编程语言.

形式语法规则

非终结符号应出现在至少一个产生式的左侧
目标符号不应该显示在任何产生式的::= 右侧
如果 LHS 出现在 RHS 中，则规则是递归的

符号约定

符号约定符号可以通过将元素括在方括号中来表示。它是元素实例的任意序列，可以通过将元素括在括号中，后跟星号符号 { … }* 来表示。

它是单条规则中可以使用符号的备选选项，必要时可以用括号（[,]）括起来。

两种符号约定：终端符号和非终端符号

1.终端：

字母表中的小写字母，例如 a、b、c，
Opera+、-、* 等符号。
标点符号，例如括号、井号、逗号
0、1、…、9 位数字
粗体字符串，如 id 或 if，任何代表单个终端符号的字符串

2.非终结符：

大写字母，例如 A、B、C
小写斜体名称：表达式或一些

上下文无关语法

CFG 是一种左递归语法，至少有一个该类型的产生式。上下文无关语法中的规则主要是递归的。语法分析器检查特定程序是否满足上下文无关语法的所有规则。如果满足，语法分析器可能会为该程序创建解析树。

expression -> expression -+ term
expression -> expression – term 
expression-> term
term  -> term * factor
term -> expression/ factor
term  -> factor factor
factor ->  ( expression )
factor -> id

语法推导

文法推导是将起始符号转化为字符串的一系列文法规则，文法推导证明该字符串属于该文法的语言。

最左推导

当输入的句型按照从左到右的顺序被扫描和替换时，这被称为最左推导。由最左推导得到的句型称为左句型。

最右推导

最右推导扫描并用产生式规则替换输入，从右到左，按顺序排列。这被称为最右推导。从最右推导得出的句子形式称为右句子形式。

语法与词法分析器

语法分析器	词法分析器
语法分析器主要处理语言的递归结构。	词法分析器简化了语法分析器的任务。
语法分析器对源程序中的标记进行处理，以识别编程语言中有意义的结构。	词法分析器识别源程序中的标记。
它从词汇分析器接收以标记形式出现的输入。	它负责确保所提供令牌的有效性语法分析器

使用语法分析器的缺点

它永远不会确定令牌是否有效
不能帮助您确定对令牌类型执行的操作是否有效
您无法决定令牌是否在使用前被声明和初始化

结语

语法分析是编译器设计过程的第二阶段，位于词法分析之后
语法分析器可帮助你将规则应用于代码
句子、词素、标记、关键字和保留字、噪声词、注释、分隔符、字符集、标识符是编译器语法分析中使用的一些重要术语
解析检查输入的字符串是否格式正确，如果格式不正确，则拒绝
解析技术分为两类：自上而下的解析、自下而上的解析
词汇、句法、语义和逻辑是解析方法过程中常见的一些错误
语法是描述语言的一组结构规则
符号约定符号可以通过将元素括在方括号中来表示
CFG 是一种左递归文法，至少有一个以下类型的产生式
语法推导是将起始符号转换为字符串的一系列语法规则
语法分析器主要处理语言的递归结构，而词法分析器则简化了语法分析器的任务 DBMS
语法分析器方法的缺点是它永远无法确定一个标记是否有效