编译原理实验语法分析

‘壹’ 编译原理中语法分析的作用是什么

语法分析是搞清楚语言含义的必要条件，只有语法搞清楚了，语句表达的意思才能得到准确理解，才能得到正确实现。

‘贰’ 编译原理语法分析实验问题

错误1：在3.txt中，第二个表达式x:=2*3，在编译器里面没有对*符号进行解释，这个应补充，或者改掉*为+。
错误2：代码中出现3次类似syn==15||16的代码，我理解应该是(syn==15)||(syn==16)
改掉这两点后代码可以正常运行。
建议：写代码是一项工作，更是一个创作过程，建议你按照代码写作规范来写，这样的代码清晰易读，易于交流和纠错。

‘叁’ 编译原理实验二 LL(1)分析法

通过完成预测分析法的语法分析程序，了解预测分析法和递归子程序法的区别和联系。使学生了解语法分析的功能，掌握语法分析程序设计的原理和构造方法，训练学生掌握开发应用程序的基本方法。有利于提高学生的专业素质，为培养适应社会多方面需要的能力。

根据某一文法编制调试 LL(1)分析程序，以便对任意输入的符号串进行分析。
构造预测分析表，并利用分析表和一个栈来实现对上述程序设计语言的分析程序。
分析法的功能是利用LL(1)控制程序根据显示栈栈顶内容、向前看符号以及LL(1)分析表，对输入符号串自上而下的分析过程。

对文法 的句子进行不含回溯的自上向下语法分析的充分必要条件是：
（1）文法不含左递归；
（2）对于文法中的每一个非终结符 的各个产生式的候选首符集两两不相交，即，若

Follow集合构造：
对于文法 的每个非终结符 构造 的算法是，连续使用下面的规则，直至每个 不再增大为止：

仅给出核心部分
(1) GrammerSymbol.java

(2) GrammerSymbols.java

(3) Grammer.java

(4) LL1Grammer.java

‘肆’ 编译原理中词法分析和语法分析的任务分别是什么

在编译原理中，语法规则和词法规则不同之处在于：规则主要识别单词,而语法主要识别多个单词组成的句子。
词法分析和词法分析程序：
词法分析阶段是编译过程的第一个阶段。这个阶段的任务是从左到右一个字符一个字符地读入源程序，即对构成源程序的字符流进行扫描然后根据构词规则识别单词(也称单词符号或符号)。词法分析程序实现这个任务。词法分析程序可以使用lex等工具自动生成。
语法分析（Syntax analysis或Parsing）和语法分析程序（Parser）
语法分析是编译过程的一个逻辑阶段。语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短语，如“程序”，“语句”，“表达式”等等.语法分析程序判断源程序在结构上是否正确.源程序的结构由上下文无关文法描述.
语义分析（Syntax analysis）
语义分析是编译过程的一个逻辑阶段. 语义分析的任务是对结构上正确的源程序进行上下文有关性质的审查, 进行类型审查.语义分析将审查类型并报告错误:不能在表达式中使用一个数组变量,赋值语句的右端和左端的类型不匹配.

‘伍’ 【编译原理】第四章：语法分析

从分析树的根节点到叶节点方向构造分析树。
即从开始符号S推导出词串w的过程。

例：

总是选择每个句型的 最左非终结符 进行替换。

总是选择每个句型的 最右非终结符 进行替换。

在自底向上的分析中，总是采用 最左规约 的方式，因此把 最左规约 称为 规范规约 ，对应的 最右推导 称为 规范推导 。

最左推导、最右推导具有唯一性。

自顶向下的语法分析采用最左推导方试，总是选择每个句型的 最左非终结符 进行替换。

由一组 过程 组成，每一个过程对应一个 非终结符 。
从文法开始符号S开始，递归调用文法中的其他非终结符，最终扫描整个输入串，完成分析。

如果其间有不唯一的产生式，就可能需要退回上一步重新尝试的情况，称为 回溯 。

预测分析 是 递归下降分析 技术的一个特例，通过输入中向前看固定个数的符号选择正确的产生式。
如果一个文法可以构造出向前看k个符号的预测分析器，称为LL(k)文法 。

预测分析不需要回溯，具有确定性。

含有 形式产生式的文法称为是 直接左递归 的。
如果一个文法中有一个非终结符A使得对某个串存在推导 ，那么这个文法是 左递归 的。其中，经过两步或以上推导产生的左递归，称为 间接左递归 的。
左递归会使递归下降分析器陷入无限循环。

文法
即
该文法是直接左递归的，会陷入无限循环。

将以上文法转换为：


即可消除左递归。事实上，这个过程把左递归转换成了右递归。

消除直接左递归的一般形式

使用代入法。

对于一个文法，通过改写产生式来 推迟决定 ，等获得足够多的输入信息再做正确的决定。

例：文法：

可以改写为：

从文法的开始符号S开始，每一步推导根据当前句型的最左非终结符A和当前输入符号α，选择正确的A-产生式。为保证分析的确定性，选出的候选式必须是唯一的。

S_文法（简单的确定型文法）

可能在某个举行中紧跟在A后面的终结符a的集合，记为 FOLLOW(A) 。
如果A是某个句型的最右符号，则将结束符“ $ ”添加到FOLLOW(A)中。

例：文法：






中，FOLLOW(B) = {a, c}

产生式 的可选集是指可以选用该产生式进行推导时对应的输入符号的集合，记为 SELECT(A->β) 。
例如
SELECT(A -> aβ)={a}
SELECT(A -> aβ | bγ)={a, b}
SELECT(A -> ε)=FOLLOW(A)

q_文法

文法符号串α串首终结符的集合，记作 FIRST(A) 。

‘陆’ 编译原理笔记17：自下而上语法分析（4）LR(0)、SLR(1) 分析表的构造

（移进项目就是指圆点右边是终结符的项目，规约项目指的就是圆点在右部最右端的项目）

LR(0) 文法可以直接通过识别活前缀的 DFA 来构造 LR 分析表

假定 C = {I ₀ , I ₁ , ... , I _n } （aka. LR(0) 项目规范族、DFA 状态集）

首先为文法产生式进行编号，拓广文法的产生式要标记为 0（这里就是后面分析表中 rj 的产生式编号 j 的由来）

然后令每个项目集 I _k 的下标 k 作为分析器的状态（行首），包含 S' → .S 的集合下标为分析器的初态（也就是 DFA 的初态，一般都是 0 ）。

下面用一个例子来说明 ACTION、GOTO 子表的构造：

SLR(1) 为解决冲突提出了一个简单的方法：通过识别活前缀的 DFA 和【简单向前看一个终结符】构造 SLR(1) 分析表。

如果我们的识别活前缀的 DFA 中存在移进-规约冲突、规约-规约冲突，都可以尝试使用这个方法来解决冲突。（这里说【尝试】，当然是因为 SLR 也只能解决一部分问题，并不是万能的灵丹妙药。。）

这里，我们拿前面那个 LR(0) 解决不了的文法来举例

该文法不是 LR(0) 文法，但是是 SLR(1) 文法。

观察上图 DFA 中的状态2，想象当我们的自动机正处于这个状态：次栈顶已经规约为 T 了，栈顶也是当前的状态 2 ，而当前剩余输入为 *。

如果这个自动机不会【往前多看一步】的话，那么对处于这个状态的自动机来说，看起来状态 2 中的移进项目和规约项目都是可选的。这就是移进-规约冲突。

想要解决这个冲突，就轮到【往前多看一步】上场了——把当前剩余输入考虑进来，辅助进行项目的选择：

对其他的冲突也使用同样的方法进行判断。

这种冲突性动作的解决办法叫做 SLR(1) 解决办法

准备工作部分，与 LR(0) 分析表的构造差不多：同样使用每个项目集的状态编号作为分析器的状态编号，也就同样用作行下标；同样使用拓广文法产生式作为 0 号产生式。

填表也和 LR(0) 类似，唯一的不同体现在对规约项的处理方法上：如果当前状态有项目 A → α.aβ 和 A → α. ，而次栈顶此时是 α 且读写头读到的是 a，那么当且仅当 a∈FOLLOW(A) 时，我们才会用 A → α 对 α 进行规约。

如果构造出来的表的每个入口都不含多重定义（也就是如上图中表格那样的，每个格子里面最多只有一个动作），那么该表就是该文法的 SLR(1) 表，这个文法就是 SLR(1) 文法。使用 SLR(1) 表的分析器叫做一个 SLR(1) 分析器。

任意的二义文法都不能构造出 SLR(1) 分析表

例：悬空 else

例：

这里的 L 可以理解为左值，R 可以理解为右值

经过计算可以确定其 DFA 如下图所示。

在 状态4 中，由于 "=" 同时存在于 FOLLOW(L) 与 FOLLOW(R) 中，因此该状态内存在移进-规约冲突，故该文法不是 SLR(1) 文法。

这样的非二义文法可以通过增加向前看终结符的个数来解决冲突（比如LL(2)、LR(2)）但这会让问题更加复杂，故一般不采用。而二义文法无论向前看多少个终结符都无法解决二义性。

‘柒’ 编译原理，递归下降子程序语法分析

没学过编译原理，看描述，是让写一个脚本执行软件。
终结符我查了下，就是不可再分的。比如iε。
输入是EGTSFI*/ε组成的字符串。
规则需要预处理。注意转意符在字符串中的效果。因为有/字符。

不会c或c++，只会c#。你可以到贴吧发帖。强人工智能吧 就挺好。算法吧有点乱。

最重要的，不要钱。

‘捌’ 如何通俗易懂地解释编译原理中语法分析的过程

分成词法分析，语法分析（LL算法，递归下降算法，LR算法），语义分析，运行时环境，中间代码，代码生成，代码优化这些部分。其实现在很多编译原理的教材都是按照85,86出版的那本龙书来安排教学内容的，所以那本龙书的内容格式几乎成了现在编译原理教材的定式，包括国内的教材也是如此。一般来说，大学里面的本科教学是不可能把上面的所有部分都认真讲完的，而是比较偏重于前面几个部分。像代码优化那部分东西，就像个无底洞一样，如果要认真讲，就是单独开一个学期的课也不可能讲得清楚。所以，一般对于本科生，对词法分析和语法分析掌握要求就相对要高一点了。

词法分析相对来说比较简单。可能是词法分析程序本身实现起来很简单吧，很多没有学过编译原理的人也同样可以写出各种各样的词法分析程序。不过编译原理在讲解词法分析的时候，重点把正则表达式和自动机原理加了进来，然后以一种十分标准的方式来讲解词法分析程序的产生。这样的做法道理很明显，就是要让词法分析从程序上升到理论的地步。

语法分析部分就比较麻烦一点了。现在一般有两种语法分析算法，LL自顶向下算法和LR自底向上算法。LL算法还好说，到了LR算法的时候，困难就来了。很多自学编译原理的都是遇到LR算法的理解成问题后就放弃了自学。其实这些东西都是只要大家理解就可以了，又不是像词法分析那样非得自己写出来才算真正的会。像LR算法的语法分析器，一般都是用工具Yacc来生成，实践中完全没有比较自己来实现。对于LL算法中特殊的递归下降算法，因为其实践十分简单，那么就应该要求每个学生都能自己写。当然，现在也有不少好的LL算法的语法分析器，不过要是换在非C平台，比如Java,Delphi,你不能运用YACC工具了，那么你就只有自己来写语法分析器。

‘玖’ 编译原理笔记7：语法分析（1）语法分析器的任务、语法错误的处理

语法分析器的两项主要任务，分别：

源程序中的错误可以分为词法/语法错误、语义错误两类。前者主要形式是命名不合法、关键字书写错误、语法结构有问题（比如缺分号、该配对的东西不配对）等；后者则可分为静态/动态两种，静态例如类型使用错误、参数使用错误等，动态语义错误则是无穷递归这类逻辑性的问题。

例如：

紧急恢复：x = a+b+d; // 丢弃掉 b 后的记号，直到遇到 +

短语级恢复： x = a+b; // 加入分号

在写程序时，要养成减少错误的好习惯：每次用变量、参数时，要在使用之前进行初始化，并在直接使用之前检查一下是否出现值为空等问题，防止出现不可预知的错误

‘拾’ 编译原理语法分析有哪几种方法

语法分析有自上而下和自下而上两种分析方法
其中
自上而下：递归下降，LL(1)
自下而上：LR(0),SLR(1),LR(1),LALR(1)