当前位置：文档库 › 第7讲语法分析_4(SLR LR1 LALR)

第7讲语法分析_4(SLR LR1 LALR)

编译原理语法分析实验二

华北水利水电学院编译原理实验报告 2010～2011学年第二学期xxxx 级计算机专业班级：xxxxx 学号：xxxxx 姓名：xxx 一、实验目的通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析方法。二、实验要求 ⑴选择最有代表性的语法分析方法，如LL（1）分析法、算符优先法或LR分析法 ⑵选择对各种常见程序语言都用的语法结构，如赋值语句（尤指表达式）作为分析对象，并且与所选语法分析方法要比较贴切。 ⑶实习时间为6小时。三、实验内容选题1：使用预测分析法（LL（1）分析法）实现语法分析：（1）根据给定文法，先求出first集合、follow集合和select集合，构造预测分析表（要求预测分析表输出到屏幕或者输出到文件）；（2）根据算法和预测分析表分析给定表达式是否是该文法识别的正确的算术表达式（要求输出归约过程）（3）给定表达式文法为： G(E): S→TE E→+TE | ε T→FK K→*FK |ε F→(S)|i (4)分析的句子为： (i+i)*i和i+i)*i 四、程序源代码 #include "stdafx.h" #include "SyntaxAnalysis.h" #include "SyntaxAnalysisDlg.h" #ifdef _DEBUG #define new DEBUG_NEW #undef THIS_FILE static char THIS_FILE[] = __FILE__; #endif /////////////////////////////////////////// // CAboutDlg dialog used for App About

实验二--语法分析-

实验二--语法分析(算符优先)-(2)

编译原理实验报告实验名称：语法分析器设计专业：计算机科学与技术姓名：田莉莉学号：201117906

语法分析—算符优先分析程序一．实验要求 ⑴ 选择最有代表性的语法分析方法，如算符优先法、递归子程序法或LR 分析法 ⑵ 选择对各种常见程序语言都用的语法结构，如赋值语句（尤指表达式）作为分析对象，并且与所选语法分析方法要比较贴切。 ⑶ 实习时间为6 学时。二．实验内容及要求（ 1）根据给定文法，先求出 FirstVt 和 LastVt 集合，构造算符优先关系表（要求算符优先关系表输出到屏幕或者输出到文件）；（ 2）根据算法和优先关系表分析给定表达式是否是该文法识别的正确的算术表达式（要求输出归约过程）（3）给定表达式文法为： G（E ' ）: E'T #E# E—E+T | T T—T*F |F F—（E）|i （4）分析的句子为 : （i+i）*i 和 i+i）*i 三．程序设计思想及实现步骤程序的设计思想：

按照编译原理教材提供的算法，本程序的设计主要实现三个主要的过程：（1）求解 FristVT 集和 LastVT 集：利用 CString 数组存放 VT 集，利用数组下标对应非终结符关系；（2）输出算符优先分析表：利用 MFC 中的 ClistCtrl 控件输出显示算符表，比利用二维数组对应其在内存中的关系。（3）利用算符优先分析表进行归约：根据教材所给算法，并对其进行实现在屏幕上输出归约过程。实现步骤： 1、为程序各变量设计存储形式，具体设计如下所示： CString m_strTElem[T_LEN]; CString m_strNTElem[NT_LEN]; // 非终结符 CMapStringToPtr m_mapProdu; // 存放产生式 CMapStringToPtr m_mapProduEX; // 存放扩展产生式 CString m_strFristVT[NT_LEN]; CString m_strLastVT[NT_LEN]; int m_nPriSheet[T_LEN+1][T_LEN+1]; // 终结符 //fristVT 集 //lastVT 集

编译原理实验二

实验二语法分析一、实验目的：设计MiniC的上下文无关文法，利用JavaCC生成调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。二、语法分析器: 按照MiniC语言的语法规则检查词法分析输出的记号流是否符合这些规则，并根据这些规则所体现出的语言中的各种语法结构的层次性。把规则写入到JavaCC的.jjt文件中，可以生成树状的层次结构。三、JavaCC: 在JavaCC的文法规范文件中，不仅可以描述语言的语法规范，而且可以描述词法规范，本次实习中，利用JavaCC以MiniC语言构造一个不含语义分析的编译器前端，包括词法分析、语法分析，并要考虑语法分析中的错误恢复问题。通过使用JavaCC, 可以体会LL(k)文法的编写特点，掌握编写JavaCC文法规范文件的方法。内容：利用JavaCC生成一个MiniC的语法分析器；要求： 1.用流的形式读入要分析的C语言程序，或者通过命令行输入源程序。 2.具有错误检查的能力，如果有能力可以输出错误所在的行号，并简单提示 3.如果输入的源程序符合MiniC的语法规范，输出该程序的层次结构的语法树本次实习仅完成以下语法范畴的语法分析： 1. 写出一个源程序中仅包含if…else, else语句的语法分析。要求能分析其自身嵌套. 其他语句可简化处理 2. 写出一个源程序中仅包含for语句的语法分析。要求能分析其自身嵌套，其他语句可简化处理 3. 写出一个源程序中仅包含while语句的语法分析。要求能分析其自身嵌套。其他语句可简化处理 4. 写出一个源程序中包含上面的12或者13或者23或者123语句的语法分析。要求能分析除其自身嵌套外，还包括相互嵌套。其他语句可简化处理具体实施步骤如下： 1.把MiniC转换为文法如下 <程序〉→ main()〈语句块〉〈语句块〉→{〈语句串〉}

编译原理实验二语法分析器LL(1)实现

编译原理程序设计实验报告 ——表达式语法分析器的设计班级：计算机1306班姓名：张涛学号：20133967 实验目标：用LL（1）分析法设计实现表达式语法分析器实验内容： ⑴概要设计：通过对实验一的此法分析器的程序稍加改造，使其能够输出正确的表达式的token序列。然后利用LL（1）分析法实现语法分析。 ⑵数据结构： int op=0; //当前判断进度 char ch; //当前字符 char nowword[10]=""; //当前单词 char operate[4]={'+','-','*','/'}; //运算符 char bound[2]={'(',')'}; //界符 struct Token { int code; char ch[10]; }; //Token定义

struct Token tokenlist[50]; //Token数组 struct Token tokentemp; //临时Token变量struct Stack //分析栈定义 { char *base; char *top; int stacksize; }; ⑶分析表及流程图

Begin PUSH(#),PUSH(E) POP(x) x ∈VT x ∈VN x=w end W=#n y NEXT(w) y n err 查LL （1）分析表空？ n PUSH （i ）err n y 逆序压栈 ⑷关键函数： int IsLetter(char ch) //判断ch 是否为字母 int IsDigit(char ch) //判断ch 是否为数字 int Iskey(char *string) //判断是否为关键字 int Isbound(char ch) //判断是否为界符 int Isboundnum(char ch) //给出界符所在token 值 int init(STack *s) //栈初始化 int pop(STack *s,char *ch) //弹栈操作 int push(STack *s,char ch) //压栈操作 void LL1(); //分析函数源程序代码：（加入注释）

实验二语法分析程序设计与实现

实验二语法分析程序设计与实现一、实验目的任选一种有代表性的语法分析方法，如算符优先法、递归下降法、LL(1)、SLR(1)、LR(1)等，通过设计、编制、调试实现一个典型的语法分析程序，对实验一所得扫描器提供的单词序列进行语法检查和结构分析，实现并进一步掌握常用的语法分析方法。二、基本实验内容与要求选择对各种常见高级程序设计语言都较为通用的语法结构——算术表达式的一个简化子集——作为分析对象，根据如下描述其语法结构的BNF定义G2[<算术表达式>]，任选一种学过的语法分析方法，针对运算对象为无符号常数和变量的四则运算，设计并实现一个语法分析程序。 G2[<算术表达式>]： <算术表达式> → <项> | <算术表达式>+<项> | <算术表达式>-<项> <项> → <因式> | <项>*<因式> | <项>/<因式> <因式> → <运算对象> | (<算术表达式>) 若将语法范畴<算术表达式>、<项>、<因式>和<运算对象>分别用E、T、F 和i代表，则G2可写成： G2[E]：E → T | E+T | E-T T → F | T*F | T/F F → i | (E) 输入：由实验一输出的单词串，例如：UCON，PL，UCON，MU，ID ······ 输出：若输入源程序中的符号串是给定文法的句子，则输出“RIGHT”，并且给出每一步分析过程；若不是句子，即输入串有错误，则输出“ERROR”，并且显示分析至此所得的中间结果，如分析栈、符号栈中的信息等，以及必要的出错说明信息。要求: 1、确定语法分析程序的流程图，同时考虑相应的数据结构，编写一个语法分析源程序。 2、将词法、语法分析合在一起构成一个完整的程序，并调试成功。 3、供测试的例子应包括符合语法规则的语句，及分析程序能判别的若干错例。对于所输入的字符串，不论对错，都应有明确的信息输出。

编译原理作业集第四章修订版

第四章语法分析—自上而下分析本章要点 1. 语法分析器的功能； 2. 自上而下分析方法，LL(1)文法 3. 递归下降分析程序构造； 4. 预测分析表的构造及预测分析过程； 5. LL(1)分析中的错误处理。本章目标理解和掌握语法分析器的功能、自上而下分析所面临的问题、LL（1）分析法、递归下降分析的构造过程、预测分析程序等内容。本章重点 1．语法分析器的功能，自上而下的基本概念 2．LL（1）文法的条件及其判别，计算first集和follow集 3．递归下降分析方法、预测分析表的构造及其预测过程。本章难点 1. 非终结符的First集合，产生式候选的First集合，非终结符的follow集合的求解； 2. 左递归消除； 3. 递归下降分析程序的编写；作业题一、单项选择题： 1. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于分析法。

a. 自左至右 b. 自顶向下 c. 自底向上 d. 自右向左 2. 上下文无关文法可以用来描述。 a. 正则表达式 b. 正规文法 c. 扩展的BNF d. 翻译模式 3. 自上而下分析面临的四个问题中，不包括 a. 需消除左递归； b. 存在回朔； c. 虚假匹配； d. 寻找可归约串 4. 语法分析器接收以________为单位的输入，并产生有关信息供以后各阶段使用。 a. 表达式； b. 产生式； c. 单词； d. 语句； 5. 自上而下分析的主旨是，对任何单词符号串，试图用一切可能的办法，从文法开始符号（根结点）出发，________。 a. 为输入串寻找最右推导； b. 为输入串寻找最左直接子树； c. 为输入串建立最右直接子树； d. 为输入串寻找最左推导； 6. 把规则T→F | T*F 表示成扩展的巴克斯范式以后，画出它的语法图应该是。图a 图b 图c 图d 7. 下列文法中，_______是LL(1)文法。 a. S →aSb|ab b. S →ab|Sab c. S →aS|b d. S →aS|a 8. 设有文法G ： S→Ap|Bq A→a|cA B→b|dB 则，First(Ap)={_______________} a. a,c b. b,d c. p, q d. A, p 一．答案：1. b ；2. c ；3. d ；4. c ；5. d ；6. 图a ；二、填空题： 1. 语法分析器的工作本质上就是按____________________，识别输入符号串是否为一个句

实验二语法分析

实验二、语法分析一、实验目的：设计MiniC的上下文无关文法，利用JavaCC生成调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。二、语法分析器: 按照MiniC语言的语法规则检查词法分析输出的记号流是否符合这些规则，并根据这些规则所体现出的语言中的各种语法结构的层次性。把规则写入到JavaCC的.jjt文件中，可以生成树状的层次结构。三、JavaCC: 在JavaCC的文法规范文件中，不仅可以描述语言的语法规范，而且可以描述词法规范，本次实习中，利用JavaCC以MiniC语言构造一个不含语义分析的编译器前端，包括词法分析、语法分析，并要考虑语法分析中的错误恢复问题。通过使用JavaCC, 可以体会LL(k)文法的编写特点，掌握编写JavaCC文法规范文件的方法。内容：利用JavaCC生成一个MiniC的语法分析器；要求： 1.用流的形式读入要分析的C语言程序，或者通过命令行输入源程序。 2.具有错误检查的能力，如果有能力可以输出错误所在的行号，并简单提示 3.如果输入的源程序符合MiniC的语法规范，输出该程序的层次结构的语法树具体实施步骤如下： 1.把MiniC转换为文法如下 Procedure()→void main() {WhileStatement()} WhileStatement()→while(Condition()){(WhileStatement()|ass ign())} assign()→= ; expression()→term() (( + | - ) term()) term()→unary() (( * | / ) unary()) unary()→| | ( expression()) Condition()→expression()( < expression() | > expression() | >= expression() | <= expression() )

编译原理_实验报告实验二__语法分析(算符优先) 2

华北水利水电学院编译原理实验报告一、实验题目：语法分析（算符优先分析程序）（1）选择最有代表性的语法分析方法算符优先法；（2）选择对各种常见程序语言都用的语法结构，如赋值语句（尤指表达式）作为分析对象，并且与所选语法分析方法要比较贴切。二、实验内容（1）根据给定文法，先求出FirstVt和LastVt集合，构造算符优先关系表（要求算符优先关系表输出到屏幕或者输出到文件）；（2）根据算法和优先关系表分析给定表达式是否是该文法识别的正确的算术表达式（要求输出归约过程）（3）给定表达式文法为： G(E’): E’→#E# E→E+T | T T→T*F |F F→(E)|i (4) 分析的句子为: (i+i)*i和i+i)*i 三、程序源代 #include #include #include #include #define SIZE 128 char priority[6][6]; //算符优先关系表数组 char input[SIZE]; //存放输入的要进行分析的句子 char remain[SIZE]; //存放剩余串 char AnalyseStack[SIZE]; //分析栈 void analyse(); int testchar(char x); //判断字符X在算符优先关系表中的位置 void remainString(); //移进时处理剩余字符串，即去掉剩余字符串第一个字符 int k; void init()//构造算符优先关系表，并将其存入数组中 {

编译原理-四章自顶向下语法分析法

第四章自顶向下语法分析方法语法分析是编译过程的核心部分。语法分析的任务是：按照文法，从源程序符号串中识别出各类语法成份，同时进行语法检查，为语义分析和代码生成作准备。执行语法分析任务的程序称为分析程序。也称为语法分析器，它是编译程序的主要子程序之一。在第二章中我们已经介绍过。通过语法分析可建立起相应的语法树。按语法树的建立方法，我们将语法分析方法分成两大类，即自顶向下分析和自底向上分析。下面，我们先介绍自顶向下分析。本章重点：自顶向下分析、LL（1）分析第一节自顶向下分析方法一、带回溯的自顶向下分析算法这是自顶向下分析的一般方法，即对任一输入符号串，试图用一切可能的方法，从识别符号出发，根据文法自上而下地为输入串建立一棵语法树。下面用一个简单例子来说明这种过程：假定有文法G[S] ： S—c A d A — ab|a 以及输入串w=cad 为了自上而下地构造w的语法树，我们首先按文法的识别符号产生根结点S, 并让指示器IP 指

向输入串的第一符号c。然后，用S的规则（此处左部为S的规则仅有一条）把这棵树发展为| （a）（b）（c）图3-1-1 图3-1-1a。我们希望用S的子结从左至右匹配整个输入串w。首先，此树的最左子结是终结符c为标志的子结，它和输入串的第一个符号相匹配。于是，我们就把IP调整为指向下一输入符号a,并让第二个子结A去进行匹配，非终结符A有二个选择，我们试着用它的第一个选择去匹配输入串，于是把语法树发展为图3-1-1b。子树A的最左子结和IP所指的符号相符，然后我们再把IP调为指向下一符号d并让A的第二个子结进入工作。但A 的第二个子结为终结符号b，与IP当前指的符号d不一致。因此，A宣告失败。这意味着A的第一个选择此刻不适用于构造w的语法树。这时，我们应该回头（回溯）看A是否还有别的选择。为了实现回溯，我们一方面应把A的第一个选择所生长的子树注销掉；另一方面，应把IP恢复为进入A时的原值，也就是让它重新指向第二输入符号a。现在我们试探用A的第二个选择，即考虑生成图3-1-1C的语法树。由于子树A只有一个子结a，而且，它和IP所指的符号相一致，于是，A

实验二--语法分析程序的设计-

实验二语法分析程序的设计姓名：学号：专业班级一、实验目的通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析中预测分析方法。二、实验内容设计一个文法的预测分析程序，判断特定表达式的正确性。三、实验要求 1、给出文法如下： G[E] E->T|E+T; T->F|T*F; F->i|(E); 2、根据该文法构造相应的LL(1)文法及LL(1)分析表，并为该文法设计预测分析程序，利用C语言或C++语言或Java语言实现； 3、利用预测分析程序完成下列功能： 1）手工将测试的表达式写入文本文件，每个表达式写一行，用“；”表示结束； 2）读入文本文件中的表达式； 3）调用实验一中的词法分析程序搜索单词； 4）把单词送入预测分析程序，判断表达式是否正确（是否是给出文法的语言），若错误，应给出错误信息； 5）完成上述功能，有余力的同学可以进一步完成通过程序实现对非LL(1)文法到LL（1）文法的自动转换（见实验二附加资料1）。四、实验环境 PC微机 DOS操作系统或Windows 操作系统 Turbo C 程序集成环境或Visual C++ 程序集成环境五、实验步骤 1、分析文法，将给出的文法转化为LL(1)文法； 2、学习预测分析程序的结构，设计合理的预测分析程序； 3、编写测试程序，包括表达式的读入和结果的输出； 4、测试程序运行效果，测试数据可以参考下列给出的数据。六、测试数据

输入数据：编辑一个文本文文件expression.txt ，在文件中输入如下内容：正确结果：（1）10; 输出：正确（2）1+2; 输出：正确（3）(1+2)*3+(5+6*7); 输出：正确（4）((1+2)*3+4 输出：错误（5）1+2+3+(*4+5) 输出：错误（6）(a+b)*(c+d) 输出：正确（7）((ab3+de4)**5)+1 输出：错误七、源代码 import java.util.*; import java.io.*; public class test2 { static String[] key_word = { "main", "if", "then", "while", "do", "int", "else" }; static String[] cal_word = { "+", "-", "*", "/", "<", ">", "{", "}", "(", ")", "[", "]", "==", "!=", "!", "=", ">=", "<=", "+=", "-=", "*=", "/=", ";" }; /* * 给定文法G[E]： E->T|E+T; T->F|T*F; F->i|(E); */ static String[] gram = { "E->TA", "A->+TA", "A->@", "T->FB", "B->*FB", "B->@", "F->P", "F->(E)" }; static String[] followE = { ")", "#" };

编译原理语法分析器实验

语法分析器的设计一、实验内容语法分析程序用LL(1)语法分析方法。首先输入定义好的文法书写文件(所用的文法可以用LL(1)分析)，先求出所输入的文法的每个非终结符是否能推出空，再分别计算非终结符号的FIRST集合，每个非终结符号的FOLLOW集合，以及每个规则的SELECT集合，并判断任意一个非终结符号的任意两个规则的SELECT 集的交集是不是都为空，如果是，则输入文法符合LL(1)文法，可以进行分析。对于文法： G[E]: E->E+T|T T->T*F|F F->i|(E) 分析句子i+i*i是否符合文法。二、基本思想 1、语法分析器实现语法分析是编译过程的核心部分，它的主要任务是按照程序的语法规则，从由词法分析输出的源程序符号串中识别出各类语法成分，同时进行词法检查，为语义分析和代码生成作准备。这里采用自顶向下的LL(1)分析方法。语法分析程序的流程图如图5-4所示。语法分析程序流程图该程序可分为如下几步：（1）读入文法（2）判断正误（3）若无误，判断是否为LL(1)文法（4）若是，构造分析表；（5）由句型判别算法判断输入符号串是为该文法的句型。三、核心思想该分析程序有15部分组成：（1）首先定义各种需要用到的常量和变量；

（2）判断一个字符是否在指定字符串中；（3）读入一个文法；（4）将单个符号或符号串并入另一符号串；（5）求所有能直接推出&的符号；（6）求某一符号能否推出‘& ’；（7）判断读入的文法是否正确；（8）求单个符号的FIRST；（9）求各产生式右部的FIRST；（10）求各产生式左部的FOLLOW；（11）判断读入文法是否为一个LL(1)文法；（12）构造分析表M；（13）句型判别算法；（14）一个用户调用函数；（15）主函数；下面是其中几部分程序段的算法思想： 1、求能推出空的非终结符集 Ⅰ、实例中求直接推出空的empty集的算法描述如下： void emp(char c){ 参数c为空符号 char temp[10];定义临时数组 int i; for(i=0;i<=count-1;i++)从文法的第一个产生式开始查找 { if 产生式右部第一个符号是空符号并且右部长度为1, then将该条产生式左部符号保存在临时数组temp中将临时数组中的元素合并到记录可推出&符号的数组empty中。 } Ⅱ、求某一符号能否推出'&' int _emp(char c) { //若能推出&，返回1；否则，返回0 int i,j,k,result=1,mark=0; char temp[20]; temp[0]=c; temp[1]='\0'; 存放到一个临时数组empt里,标识此字符已查找其是否可推出空字如果c在可直接推出空字的empty[]中,返回1 for(i=0;;i++) { if(i==count) return(0); 找一个左部为c的产生式 j=strlen(right[i]); //j为c所在产生式右部的长度 if 右部长度为1且右部第一个字符在empty[]中. then返回1(A->B,B可推出空) if 右部长度为1但第一个字符为终结符,then 返回0(A->a,a为终结符) else

LL1语法分析实验报告

LL(1)语法分析一，实验名称：实现LL分析。二，实验要求：输入任意文法消除左递归消除左因子测试任意输入语句是否合法数据结构描述算法说明输出first集合输出follow集合输出LL(1)表三．设计原理及算法描述所谓LL（1）分析法，就是指从左到右扫描输入串（源程序），同时采用最左推导，且对每次直接推导只需向前看一个输入符号，便可确定当前所应当选择的规则。实现LL（1）分析的程序又称为LL（1）分析程序或LL1（1）分析器。一个文法要能进行LL（1）分析，那么这个文法应该满足：无二义性，无左递归，无左公因子。当文法满足条件后，再分别

构造文法每个非终结符的FIRST和FOLLOW集合，然后根据FIRST和FOLLOW集合构造LL（1）分析表，最后利用分析表，根据LL(1)语法分析构造一个分析器。LL（1）的语法分析程序包含了三个部分，总控程序，预测分析表函数，先进先出的语法分析栈，本程序也是采用了同样的方法进行语法分析，该程序是采用了C语言来编写，其逻辑结构图如下： LL（1）预测分析程序的总控程序在任何时候都是按STACK栈顶符号X和当前的输入符号a做哪种过程的。对于任何（X，a），

总控程序每次都执行下述三种可能的动作之一：（１）若X = a =‘#’，则宣布分析成功，停止分析过程。（２）若X = a ‘#’，则把X从STACK栈顶弹出，让a指向下一个输入符号。（３）若X是一个非终结符，则查看预测分析表M。若M[A，a]中存放着关于X的一个产生式，那么，首先把X弹出STACK 栈顶，然后，把产生式的右部符号串按反序一一弹出STACK 栈（若右部符号为ε，则不推什么东西进STACK栈）。若M[A，a]中存放着“出错标志”，则调用出错诊断程序ERROR。事实上，LL（1）的分析是根据文法构造的，它反映了相应文法所定义的语言的固定特征，因此在LL（1）分析器中，实际上是以LL（1）分析表代替相应方法来进行分析的。 2．构造LL(1)分析表考查文法G[E]： E→E+T | T T→T*F | F F→( E ) | i | x | y 我们容易看出此文法没有左公因子也没有二义性，但却存在两个直接左递归，这里我们利用引入新非终结符的方法来消除它使方法满足要求，即：对形如：U→Ux|y的产生式（其中x,y V+ ，y不以U开头），引入一个新的非终结符U’后，可以等价地改写成为：

编译原理实验二-语法分析器的设计

集美大学计算机工程学院实验报告课程名称：编译原理班级：指导教师：姓名：实验项目编号：实验二学号：实验项目名称：语法分析器的设计实验成绩：一、实验目的通过完成预测分析法的语法分析程序，了解预测分析法和递归子程序法的区别和联系。使了解语法分析的功能，掌握语法分析程序设计的原理和构造方法，训练掌握开发应用程序的基本方法。二、实验内容 ◆根据某一文法编制调试 LL （ 1 ）分析程序，以便对任意输入的符号串进行分析。 ◆构造预测分析表，并利用分析表和一个栈来实现对上述程序设计语言的分析程序。 ◆分析法的功能是利用LL（1）控制程序根据显示栈栈顶内容、向前看符号以及LL（1）分析表，对输入符号串自上而下的分析过程。三、实验要求 1、编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。 2、如果遇到错误的表达式，应输出错误提示信息。四、实验设计方案 1、设计思想（1）、LL（1）文法的定义 LL(1)分析法属于确定的自顶向下分析方法。LL(1)的含义是：第一个L表明自顶向下分析是从左向右扫描输入串，第2个L表明分析过程中将使用最左推导，1表明只需向右看一个符号便可决定如何推导，即选择哪个产生式(规则)进行推导。 LL(1)文法的判别需要依次计算FIRST集、FOLLOW集和SELLECT集,然后判断是否为LL(1)文法,最后再进行句子分析。需要预测分析器对所给句型进行识别。即在LL(1)分析法中，每当在符号栈的栈顶出现非终极符时，要预测用哪个产生式的右部去替换该非终极符；当出现终结符时，判断其与剩余输入串的第一个字符是否匹配，如果匹配，则继续分析，否则报错。LL(1)分析方法要求文法满足如下条件：对于任一非终极符A的两个不同产生式A→α,A→β，都要满足下面条件：SELECT(A→α)∩SELECT(A→β)=?

实验二：语法分析实验

实验二语法分析器的设计与实现一、实验目的: 加深对语法分析器工作过程的理解;加强对递归下降法实现语法分析程序的掌握;能够采用一种编程语言实现简单的语法分析程序;能够使用自己编写的分析程序对简单的程序段进行语法翻译。二、实验内容: 在实验1的基础上,用递归下降分析法编制语法分析程序,语法分析程序的实现可以采用任何一种编程工具。三、实验要求: 1. 对语法规则有明确的定义; 2. 编写的分析程序能够进行正确的语法分析; 3. *对于遇到的语法错误,能够做出简单的错误处理,给出简单的错误提示,保证顺利完成语法分析过程; 4. 实验报告要求用文法的形式对语法定义做出详细说明,说明语法分析程序的工作过程,说明错误处理的实现*。四、实验学时:6学时五、实验步骤: 1. 定义目标语言的语法规则; 2. 根据语法规则输入语句段,用递归下降分析的方法进行语法分析,直到结束;

每个非终结符有对应的子程序的定义,首先在分析过程中,当需要从某个非终结符出发进行展开(推导)时,就调用这个非终结符对应的子程序。 4. 具体实现时几点提示: (1)当遇到终结符,编写:if(当前读到的输入符号=i) 读入下一个输入符号 (2)当遇到非终结符E时,编写语句:调用E() (3)当遇到E’-->ε编写语句if(当前读到的输入符号不属于Follow(E’)) Error(); (4)当某个非终结符的规则有多个候选式时,按LL(1)文法的条件能唯一的选择一个候选式进行推导。例:(1)只含有一个字符的形式: i a (2) 含有‘+’的形式: i+i i+i+i i+ +++

聊城大学编译原理实验二语法分析器

LIAOCHENG UNIVERSITY 计算机学院实验报告【2016 ～2017学年第2学期】【一、基本信息】【实验课程】编译原理【设课形式】独立□非独立√【课程学分】 4 【实验项目】实验二语法分析器的设计【项目类型】基础□综合√设计□研究创新□其它[ ] 【项目学时】 4 【学生姓名】【学号】【系别专业】软件开发【实验班组】级班组台【同组学生】【实验室名】综合实验楼【实验日期】【报告日期】【二、实验教师对报告的最终评价及处理意见】实验成绩：（涂改无效）指导教师签名：年月日注：要将实验项目、实验课程的成绩评定及课程考核办法明确告知学生，并报实验管理中心备案

实验内容和原理或涉及的知识点（综合性实验）： 1. 输入任意文法，改写文法使其成为LL(1)文法。 2. 构造文法的预测分析表； 3. 设计堆栈和预测分析表的机内表示； 4. 设计并书写语法分析程序； 5. 调试并运行语法分析程序； 6. 实验结果分析 ●分析程序中文法存储所采用的数据结构 ●分析结果并写出自己的心得体会提示：对于所选定的分析方法，如有需要，应选择一种合适的数据结构，以构造所给文法的机内表示。

T→FW’| ε W’→MFW’| ε F→( E ) | i M→* | / 2. 构造文法的预测分析表； i + - + / ( ) # E E->TE E->TE’ E’E’->ATE’E’->ATE’E’->?E’->?T T->FT’T->FT’ T’T’->?T’->?T’->MFT’T’->MFT’T’->?T’->? F F->i F->(E) A A->+ A-> M M->* M->/ 3.设计堆栈和预测分析表的机内表示；堆栈表示：预测分析表的机内表示:

编译原理实验报告5-语法分析程序的设计(2)

实验5 语法分析程序的设计（2）一、实验目的通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析中算法优先分析方法。二、实验内容设计一个文法的算法优先分析程序，判断特定表达式的正确性。三、实验要求 1、给出文法如下： G[E] E->T|E+T; T->F|T*F; F->i|(E); 2、计算机中表示上述优先关系，优先关系的机内存放方式有两种1）直接存放，2）为优先关系建立优先函数，这里由学生自己选择一种方式； 1、给出算符优先分析算法如下： k:=1; S[k]:=‘#’; REPEAT 把下一个输入符号读进a中； IF S[k]∈V T THEN j:=k ELSE j:=k-1; WHILE S[j] a DO BEGIN REPEAT Q:=S[j]; IF S[j-1]∈V T THEN j:=j-1 ELSE j:=j-2 UNTIL S[j] Q 把S[j+1]…S[k]归约为某个N；

k:=j+1; S[k]:=N; END OF WHILE; IF S[j] a OR S[j] a THEN BEGIN k:=k+1;S[k]:=a END ELSE ERROR UNTIL a=‘#’ 1、根据给出算法，利用适当的数据结构实现算符优先分析程序； 2、利用算符优先分析程序完成下列功能： 1）手工将测试的表达式写入文本文件，每个表达式写一行，用“；”表示结束； 2）读入文本文件中的表达式； 3）调用实验2中的词法分析程序搜索单词； 4）把单词送入算法优先分析程序，判断表达式是否正确（是否是给出文法的语言），若错误，应给出错误信息； 5）完成上述功能，有余力的同学可以对正确的表达式计算出结果。四、实验环境 PC 微机 DOS 操作系统或 Windows 操作系统 Turbo C 程序集成环境或 Visual C++ 程序集成环境五、实验步骤 1、分析文法中终结符号的优先关系； 2、存放优先关系或构造优先函数； 3、利用算符优先分析的算法编写分析程序； 4、写测试程序，包括表达式的读入和结果的输出； 5、程序运行效果，测试数据可以参考下列给出的数据。六、测试数据输入数据：编辑一个文本文文件expression.txt ，在文件中输入如下内容：

语法分析器实验报告2

一、实验目的设计、编制并调试一个语法分析程序，加深对语法分析原理的理解。二实验要求要求语法分析器的输入是单词串(含词的字符串形式、在源文件中的起止位置、词的类别)，输出是源程序中各句子的单词起止编号、句子的语法树。三实验内容以下不同语法分析器中任选一个： 1. 2. 3. 4. 递归下降分析器。可分解为：文法输入及解析、消除左递归、提取左公共因子、产生式匹配。 LL(1)分析器。可分解为：文法输入及解析、分析表构造(含 SELECT 集求解)、主控程序、语法树展示。算符优先文法分析器。可分解为：文法输入及解析、分析表构造、主控程序、语法树展示。 LR(1)分析器。可分解为：文法输入及解析、分析表构造(含项目及项目簇集求解)、主控程序、语法树展示。四、实验步骤给定的文法G[E] E->TE' E'->+TE' | ￡ T->FT' T'->*F T ' | ￡ F->(E) | i 采用递归下降分析法编写语法分析程序及 LL (1)语法分析法编写语法分析程序。实验代码： #in clude #in clude #in clude #defi ne N 100 int seek Prod(i nt stackT op ,i nt inpu tstrT op); //char inpu tstr[10]="i*i+i#"; char inpu tstr[20]; char stack[10]=""; typ edef struct p roducti on{ char leftChar; char rightChars[4]; char allChars[8]; }P rod; Prod p roduct ion s[8]; void in it(); int stack Pu sh(i nt *top, Prod p rod); int matchi ng(i nt *top, char *inpu tstr); int mai n()

昆明理工大学_编译原理_实验二_语法分析器

昆明理工大学信息工程与自动化学院学生实验报告（2011 —2012 学年第 1 学期）课程名称：编译原理开课实验室： 445 2011年 12 月 19日年级、专业、班学号成绩实验项目名称语法分析器指导教师严馨教师评语该同学是否了解实验原理： A.了解□ B.基本了解□ C.不了解□ 该同学的实验能力： A.强□ B.中等□ C.差□ 该同学的实验是否达到要求： A.达到□ B.基本达到□ C.未达到□ 实验报告是否规范： A.规范□ B.基本规范□ C.不规范□ 实验过程是否详细记录： A.详细□ B.一般□ C.没有□ 教师签名：年月日一、实验目的及内容实验目的：编制一个语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析。实验内容：在上机(一)词法分析的基础上,采用递归子程序法或其他适合的语法分析方法,实现其语法分析程序。要求编译后能检查出语法错误。已知待分析的C语言子集的语法，用EBNF表示如下： <程序>→main()<语句块> <语句块> →‘{’<语句串>‘}’ <语句串> → <语句> {; <语句> }; <语句> → <赋值语句> |<条件语句>|<循环语句> <赋值语句>→ID=<表达式>

<条件语句>→if‘(‘条件’)’<语句块> <循环语句>→while’(‘<条件>’)‘<语句块> <条件> → <表达式><关系运算符> <表达式> <表达式> →<项>{+<项>|-<项>} <项> → <因子> {* <因子> |/ <因子>} <因子> →ID|NUM| ‘(’<表达式>‘)’ <关系运算符> →<|<=|>|>=|==|!= 二、实验原理及基本技术路线图（方框原理图或程序流程图）

实验二--语法分析程序设计与实现

实验二语法分析程序设计与实现一、实验目的任选一种有代表性的语法分析方法，如算符优先法、递归下降法、LL(1)、SLR(1)、LR(1)等，通过设计、编制、调试实现一个典型的语法分析程序，对实验一所得扫描器提供的单词序列进行语法检查和结构分析，实现并进一步掌握常用的语法分析方法。二、基本实验内容与要求选择对各种常见高级程序设计语言都较为通用的语法结构——算术表达式的一个简化子集——作为分析对象，根据如下描述其语法结构的BNF定义G2[<算术表达式>]，任选一种学过的语法分析方法，针对运算对象为无符号常数和变量的四则运算，设计并实现一个语法分析程序。 G2[<算术表达式>]： <算术表达式> → <项> | <算术表达式>+<项> | <算术表达式>-<项> <项> → <因式> | <项>*<因式> | <项>/<因式> <因式> → <运算对象> | (<算术表达式>) 若将语法范畴<算术表达式>、<项>、<因式>和<运算对象>分别用E、T、F 和i代表，则G2可写成： G2[E]：E →T | E+T | E-T T →F | T*F | T/F F → i | (E) 输入：由实验一输出的单词串，例如：UCON，PL，UCON，MU，ID ······ 输出：若输入源程序中的符号串是给定文法的句子，则输出“RIGHT”，并且给出每一步分析过程；若不是句子，即输入串有错误，则输出“ERROR”，并且显示分析至此所得的中间结果，如分析栈、符号栈中的信息等，以及必要的出错说明信息。

要求: 1、确定语法分析程序的流程图，同时考虑相应的数据结构，编写一个语法分析源程序。 2、将词法、语法分析合在一起构成一个完整的程序，并调试成功。 3、供测试的例子应包括符合语法规则的语句，及分析程序能判别的若干错例。对于所输入的字符串，不论对错，都应有明确的信息输出。三、问题分析及源程序 LL1文法: 改写文法为: E->TG e G>+TG g T->FS t F->-TG g1 G->^ g2 S->*FS s T->/FS s1 S->^ s2 F->(E) f G->i f1 分析表： i + - * / ( ) # E e e G g g1 g2 g2 T t t S s2 s2 s s1 s2 s2 F f1 f LL1源程序

实验二--语法分析(算符优先)

实验二语法分析算符优先分析程序一．实验要求 ⑴选择最有代表性的语法分析方法，如算符优先法、递归子程序法或LR分析法 ⑵选择对各种常见程序语言都用的语法结构，如赋值语句（尤指表达式）作为分析对象，并且与所选语法分析方法要比较贴切。 ⑶实习时间为6学时二．实验内容及要求（1）根据给定文法，先求出FirstVt和LastVt集合，构造算符优先关系表（要求算符优先关系表输出到屏幕或者输出到文件）；（2）根据算法和优先关系表分析给定表达式是否是该文法识别的正确的算术表达式（要求输出归约过程）（3）给定表达式文法为： G(E’): E’→#E# E→E+T | T T→T*F |F F→(E)|i (4)分析的句子为: (i+i)*i和i+i)*i 三、实验主要代码 # define MAX 100

char *SR;//输入串 char SY[MAX];//移近或规约后剩余串 char S[MAX];//堆栈 char grammer[10][30];//保存输入的语法规则 char chanshengshi[20][10]; char feizhongjie[10];//存放非终结符 char zhongjie[15];//存放终结符 int numf=0;//非终结符个数 int num=0;//终结符个数 int M=0;//转换后产生式个数 char Relation[6][6];//存放优先关系 int FIRSTVT[3][6];//存放firstvt集 int LASTVT[3][6];//存放lastvt集 int type(char s)//在终结符串里查找字符a若a在其中返回下标，否则返回-1 { int len=strlen(zhongjie); int tp=-1; for(int i=0;i'Z') { cout<<"该文法不是算符文发!"<

第7讲 语法分析_4(SLR LR1 LALR)

编译原理 语法分析实验二