下载文档原格式
编译原理期末复习题(包含上一份N多答案)(总28页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--编译原理复习题一、填空题：1、编译方式与解释方式的根本区别在于（是否生成目标代码）。
2、对编译程序而言，输入数据是（源程序），输出结果是（目标程序）。
3、如果编译程序生成的目标程序是机器代码程序，则源程序的执行分为两大阶段：（编译阶段）和（运行阶段）。
4、如果编译程序生成的目标程序是汇编语言程序，则源程序的执行分成三个阶段：（编译阶段）、（汇编阶段）和（运行阶段）。
5、自顶向下语法分析方法会遇到的主要问题有（回溯）和（（左递归带来的）无限循环）。
6、LL(k)分析法中，第一个L的含义是（从左到右进行分析），第二个L的含义是（每次进行最左推导），“k”的含义是（向输入串中查看K个输入符号）。
7、LL(1)分析法中，第一个L的含义是（从左到右进行分析），第二个L的含义是（每次进行最左推导），“1”的含义是（向输入串中查看1个输入符号）。
8、自顶向下语法分析方法的基本思想是：从（识别符号）出发，不断建立（直接推导），试图构造一个推导序列，最终由它推导出与输入符号相同的（符号串）。
9、自底向上语法分析方法的基本思想是：从待输入的符号串开始，利用文法的规则步步向上进行（直接归约），试图（归约）到文法的（识别符号|开始符号）。
10、LR(0)分析法的名字中，“L”的含义是（从左到右进行分析），“R”的含义是（采用最右推导的逆过程---最左归约），“0”的含义是（向貌似句柄的符号串后查看0个输入符号）。
11、LR(1)分析法的名字中，“L”的含义是（从左到右进行分析），“R”的含义是（采用最右推导的逆过程---最左归约），“1”的含义是（向貌似句柄的符号串后查看1个输入符号）。
12、SLR(1)分析法的名字中，“S”的含义是（简单的），“L”的含义是（从左到右进行分析），“R”的含义是（采用最右推导的逆过程---最左归约），“1”的含义是（向貌似句柄的符号串后查看1个输入符号）。
1.给出语言{a n b n a m b m | n,m≥0}的一个上下文无关文法。
(6分)解：G[S]：S—>ABA—>aAb |εB—>aBb |ε2.给出语言{1 n 0 m 1 m0 n | n,m≥0}的一个上下文无关文法。
解：G[S]：S—>1S0 | AA—>0A1 |ε3.P48 第6题（5）、（6）.画语法树6、已知文法G：<表达式>::=<项>｜<表达式>＋<项><项>::=<因子>｜<项>*<因子><因子>::=（<表达式>）｜i（５）i+(i+i) （６）i+i*i解：(5)语法树：（6）语法树：4.P48第13题直接短语等13、一个上下文无关文法生成句子abbaa的推导树如下：(3)求直接短语解：直接短语有：a ε bP102例题6.1及其分析.( 后加画语法树)例6.1 设文法G[S]为：(1)S—>aAcBe(2)A—>b(3)A—>Ab(4)B—>d对输入串abbcde#进行分析，检查该符号串是否是G[S]的句子。
步骤符号栈输入符号串动作（1）# abbcde# 移进（2）#a bbcde# 移进（3）#ab bcde# 归约（A—>b）（4）#aA bcde#移进（5）#aAb cde# 归约（A—>Ab）（6）#aA cde# 移进（7）#aAc de# 移进（8）#aAcd e# 归约（B—>d）（9）#aAcB e# 移进（10）#aAcBe # 归约（S—>aAcBe）（11）#S # 接受一、计算分析题（60%）1、正规式→ NFA→ DFA→最简DFAP72第1题（1）、（4）；第一题1、构造下列正规式相应的DFA.（1）1(0|1)*101解：先构造NFA0 1S AA A ABAB AC ABAC A ABZABZ AC AB除S，A外，重新命名其他状态，令AB为B、AC为C、ABZ为D，因为D含有Z（NFA的终态），所以0 1S AA A BB C BC A DD C B(4) b((ab)*|bb)*ab解：先构造NFA得到DFA如下所示：P72第4题（a）4、把下图确定化和最小化解：确定化：a b0 01 101 01 11 0、{1}，其中A为初态，A，B为终态，因此有：a bA B CB B CC A最小化：：初始分划得终态组{A,B}，非终态组{C}Π0：{A,B}，{C}，对终态组进行审查，判断A和B是等价的，故这是最后的划分。
《编译原理》模拟试题一一、是非题(请在括号内，正确的划错误的划X)(每个2分，共20分)1•计算机高级语言翻译成低级语言只有解释一种方式。
(X)2.在编译中进行语法检查的目的是为了发现程序中所有错误。
(X)3.甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。
(丁 )4.正则文法其产生式为A->a , A->Bb, A.BGVN , a、beVT o (X)5.每个文法都能改写为LL(1)文法。
(V)6.递归下降法允许任一非终极符是直接左递归的。
(V)7.算符优先关系表不一定存在对应的优先函数。
(X)8.自底而上语法分析方法的主要问题是候选式的选择。
(X)9.LR法是自顶向下语法分析方法。
(X)10.简单优先文法允许任意两个产生式具有相同右部。
(X)二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分)1.一个编译程序中，不仅包含词法分析，_____ ,中间代码生成，代码优化，目标代码生成等五个部分。
A.()语法分析B.()文法分析C.()语言分析D.()解释分析2.词法分析器用于识别_____ oA.()字符串B.()语句C.()单词D.()标识符3 •语法分析器则可以发现源程序中的______ oA.()语义错误B.()语法和语义错误C.()错误并校正D.()语法错误4.下面关于解释程序的描述正确的是。
(1) 解释程序的特点是处理程序时不产生目标代码(2) 解释程序适用于COBOL 和FORTRAN 语言(3) 解释程序是为打开编译程序技术的僵局而开发的A. ( ) (1) (2)B. () (1)C. () (1)⑵(3)D.()⑵⑶5. _________________________________________ 解释程序处理语言时，大多数采用的是 ___________________________________ 方法。
编译原理期末考试题(含答案)1. 请简要解释编译原理的定义和作用。
编译原理是研究将高级语言源程序转化为等价的目标程序的一门学科。
它的主要作用是将高级语言的源代码翻译为计算机能够执行的目标代码，从而实现程序的运行。
2. 请列举并解释编译过程的各个阶段。
- 词法分析：将源代码划分为一个个词法单元，如变量、关键字等。
- 语法分析：根据语法规则，将词法单元组合为语法树，检查语法结构是否正确。
- 语义分析：对语法树进行语义检查，如类型匹配、作用域等。
- 中间代码生成：将语法树转化为中间代码表示形式，方便后续优化。
- 代码优化：对中间代码进行优化，提高程序执行效率。
- 目标代码生成：将优化后的中间代码转化为目标机器代码。
3. 请解释符号表在编译过程中的作用。
符号表是编译器在编译过程中用来管理变量、函数、类型等标识符的数据结构。
它的主要作用是记录标识符的相应属性，如类型、作用域等，以便在后续的语法、语义分析以及代码生成过程中进行查找、检查等操作。
4. 请简要解释LL(1)文法的定义和特点。
LL(1)文法是一种上下文无关文法，它具有以下特点：- 对于给定的非终结符，它的产生式右部的首符号不相同。
- 对于给定的产生式右部的首符号，它的产生式右部不相同。
- 通过向前查看一个符号，就能确定所选用的产生式。
5. 请简要解释词法分析器的作用和实现方式。
词法分析器的主要作用是将源代码分解为一个个词法单元，如变量名、关键字等。
它的实现方式一般采用有限自动机，通过定义正则表达式描述各个词法单元的模式，然后根据模式匹配的结果生成相应的词法单元。
答案仅为参考，请以实际考试为准。
编译原理期末试题(含答案+大题集+重要知识点)《编译原理》期末试题一、是非题 1．编译程序是对高级语言程序的解释执行。
(× )2．一个有限状态自动机中，有且仅有一个唯一的终态。
(×) 3．一个算符优先文法可能不存在算符优先函数与之对应。
(√ ) 4．语法分析时必须先消除文法中的左递归。
(×) 5．LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。
(√) 6．逆波兰表示法表示表达式时无须使用括号。
(√ ) 7．静态数组的存储空间可以在编译时确定。
(×)8．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。
(×) 9．两个正规集相等的必要条件是他们对应的正规式等价。
(× ) 10．一个语义子程序描述了一个文法所对应的翻译工作。
(×)二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分) 1．词法分析器的输出结果是_____。
A．( ) 单词的种别编码B．( ) 单词在符号表中的位置 C．( ) 单词的种别编码和自身值 D．( ) 单词自身值 2．正规式 M 1 和 M 2 等价是指_____。
A．( ) M1和M2的状态数相等B．( ) M1和M2的有向边条数相等 C．( ) M1和M2所识别的语言集相等D．( ) M1和M2状态数和有向边条数相等 3．文法G：S →xSx|y所识别的语言是_____。
第1页共6页A．( ) xyx B．( ) (xyx)* C．( ) xnyxn(n≥0) D．( ) x*yx* 4．如果文法G是无二义的，则它的任何句子α_____。
A．( )最左推导和最右推导对应的语法树必定相同B．( ) 最左推导和最右推导对应的语法树可能不同C．( ) 最左推导和最右推导必定相同D．( )可能存在两个不同的最左推导，但它们对应的语法树相同 5．构造编译程序应掌握______。
编译原理期末试题及答案一、选择题（每题2分，共20分）1. 编译器的主要功能是将（）代码转换成（）代码。
A. 高级语言，低级语言B. 高级语言，机器语言C. 汇编语言，机器语言D. 机器语言，汇编语言答案：B2. 编译过程中，词法分析的输出是（）。
A. 语法树B. 语法分析表C. 词法单元D. 抽象语法树答案：C3. 在编译原理中，语法分析通常采用（）方法。
A. 递归下降分析B. 动态规划C. 贪心算法D. 回溯算法答案：A4. 语义分析的主要任务是（）。
A. 检查语法错误B. 生成中间代码C. 检查语义错误D. 优化代码答案：C5. 编译器的优化通常发生在（）阶段。
A. 词法分析B. 语法分析C. 语义分析D. 代码生成答案：D6. 编译器的前端主要负责（）。
A. 代码生成B. 代码优化C. 语法分析D. 目标代码生成答案：C7. 编译器的后端主要负责（）。
A. 代码生成B. 代码优化C. 语法分析D. 词法分析答案：A8. 编译原理中，LL(1)分析方法的特点是（）。
A. 左到右，最右推导B. 左到右，最左推导C. 右到左，最右推导D. 右到左，最左推导答案：B9. 编译原理中，LR(1)分析方法的特点是（）。
A. 左到右，最右推导B. 左到右，最左推导C. 右到左，最右推导D. 右到左，最左推导答案：B10. 编译原理中，语法制导翻译的主要思想是（）。
A. 根据语法树的结构进行翻译B. 根据词法单元进行翻译C. 根据语法分析表进行翻译D. 根据语义分析表进行翻译答案：A二、填空题（每题2分，共20分）1. 编译器中，用于表示语法规则的产生式通常由非终结符、产生符号和（）组成。
答案：产生式右侧2. 在编译原理中，一个文法是（）的，如果它的任何两个产生式都不会导致相同的句柄。
答案：无二义性3. 编译器的词法分析阶段通常使用（）算法来识别和分类词法单元。
答案：有限自动机4. 语法分析阶段，如果一个文法是左递归的，编译器需要使用（）技术来消除左递归。
<编译原理>历年试题及答案一．（每项选择2分，共20分）选择题1．将编译程序分成若干个“遍”是为了_b__。
a.提高程序的执行效率b.使程序的结构更加清晰c.利用有限的机器内存并提高机器的执行效率d.利用有限的机器内存但降低了机器的执行效率2．构造编译程序应掌握__d__。
a.源程序b.目标语言c.编译方法d.以上三项都是3．变量应当c＿。
a.持有左值b.持有右值c.既持有左值又持有右值d.既不持有左值也不持有右值4．编译程序绝大多数时间花在_d___上。
a.出错处理b.词法分析c.目标代码生成d.管理表格5．词法分析器的输出结果是_c___。
a.单词的种别编码b.单词在符号表中的位置c.单词的种别编码和自身值d.单词自身值6．正规式MI和M2等价是指__c__。
a.MI和M2的状态数相等b.Ml和M2的有向弧条数相等。
C.M1和M2所识别的语言集相等 d.Ml和M2状态数和有向弧条数相等7．中间代码生成时所依据的是—c。
a．语法规则b．词法规则c．语义规则d．等价变换规则8．后缀式ab+cd+/可用表达式__b_来表示。
a．a+b/c+d b．(a+b)/(c+d)c．a+b/(c+d)d．a+b+c/d9．程序所需的数据空间在程序运行前就可确定，称为____c_＿管理技术。
a.动态存储b.栈式存储c.静态存储d.堆式存储10.堆式动态分配申请和释放存储空间遵守___d____＿原则。
a.先请先放b.先请后放c.后请先放d.任意二（每小题10分，共80分）简答题1.画出编译程序的总体结构图，简述各部分的主要功能。
2.已知文法G[E]:E→ET+|T T→TF*|F F→F^|a试证：FF^^*是文法的句型，指出该句型的短语、简单短语和句柄.3．为正规式(a|b)*a(a|b)构造一个确定的有限自动机。
4．设文法G(S)：S→(L)|a S|aL→L，S|S(1)消除左递归和回溯；(2)计算每个非终结符的FIRST和FOLLOW；(3)构造预测分析表。
《编译原理》期末复习资料【题1】(此题中第一个空愉入Q可臥省略，V即①可以眷略渝Ia Ib① 1,2,32,3,42,3,5② 2,3,42,3,4,6,7,82,3,5③ 2,3,52,3,42,,3,5,6,7,8④ 2,3,4,6,7,82,3,4,6,7,82,3,5,7,8⑤ 2,3,5,6,7,82,3,4,7,82,3,5,6,7,8⑥ 2,3,5,7,82,3,4,7,82,3,5,6,7,8⑦ 2,3,4,7,82,3,4,6,7,82,3,5,7,8Ia Ib1232431. ( a|b) * (aa|bb) (a|b) *画出状态转换图。
(1)A={1,2,3} , B={4,5,6,7} Aa={2,4} X(2)A={1,3} , B={2} , C={4,5,6,7} Aa={2} B, Ab={3,5} X(3)A={1} , B={2} , C={3},D={4,5,6,7}(单元素可以不用看，必有，古先看D), Ba={4} D , Bb={3} C, Ca={2} Cb={5} C,则有2. ( a*|b* ) b (ba) *的状态转换图。
Ia lb① 1,2,3,42,43,4,5,6,8②2,42,45,6,8③ 3,4,5,6,8---3,4,5,6,7,8④ 5,6,8---7⑤ 3,4,5,6,7,86,83,4,5,6,7,8⑥76,8---⑦6,8---7la lb1232243—54—657567—7—6abA B CB D CC B DD D D新的状态转换图如下:化简：（用终结状态与非终结状态，然后输出状态一致分一类） (1) A={1,2,6} , B={3,4,5,7} Aa={2} X(2)A={1,2} , B={6} , C={3,4,7} , D={5} Cb={5,6} X(只要有一个不属于任何一个集合，就不行) (3) A={1,2} , B={6} , C={3} , D={4,7} , E={5} Ab={3,4} X(4) A={1} , B={2} , C={6} , D={3} , E={4,7} , F={5}Aa={2} B , Ab={3} D , Ba={2} B , Bb={4}正则表达式： a , a | b, ab,(ab) , (a |b) ,a(a|b) , a | a b,a | ab*Ca={7} E , Db={5}F , Eb={6} C , Fa={7}E , Fb={5} Fab A B D B B E C E --- D --- F E--- C FEFb［注意事项］:［知识要点］:a , a, aa, aaa,a a ；a |b(a或b) a,b ；ab(a禾口b) ab ；ab a | ba | b合}a | ab ab的情2aab开始2ac b开躺终结a终结幵始ab开始终结2{a 和若 ab, abab, ababab a |ba a |b a, b, ab,aab, aaab, aaaab a | b a | ba | a ba,b, aab, aabb, baba个（包括 o{a 和a 后跟若 a | ba aaa |ba, ab, abb, abbb,abbbb,个a （包括0的情形）后跟一个 b 构成的符号串集7Vrvb 构成的符号串集合} 状态转换图（有穷状态自动机）是最左边一个字母一定是 a ，其余字母为a 、b 的任意组合，不包括终结【题2】1•求如下简单算术表达式文法G enr中语法变量的FOLLOW集。
四川大学期末考试试题A (闭卷)(2012-2013学年第2学期)一．简答题1.符号表的作用是什么？为了达到对其插入删除等操作的复杂度为O(1)，需将其组织成什么数据结构。
2.分析树和语法书的区别。
3.什么是正规集。
4.什么叫句子，什么叫句型。
5.二义文法一定不是（1）二．给定文法S→AA→B→y1.画出句子的分析树2.给出句子的最右推导三．给定正则表达式（）*1.使用构造法构造等价的。
2.用子集法对（1）得到的进行确定化和最小化，得到等价的最小。
3.使用双层多分支语句实现（2）得到的。
写出伪代码。
四．给定文法→→()→→0|1写出递归下降子程序的伪代码。
五．给定文法S→[]X→Y→1.对文法中的每一个非终结符构造集和集。
2.构造（1）分析表3.基于分析表，使用(1)对句子[]进行自顶向下的语法分析，给出每一步的动作及分析栈和输入串的变化情况。
六．给定文法E→T→T*F→(E)1.构造（0）项目的：2.构造（1）的分析表3.利用2得到的分析表对*进行自顶向下的语法分析。
七．1.给出构造集合的算法描述2.给出（1）算法的描述四川大学期末考试试题(闭卷)(2010-2011学年第2学期)1. 简答题(12分)(1) 编译器的前端和后端分别包括哪几个阶段？前后端分开有什么好处？(2) 解释器和编译器有什么本质区别？(3) 词法分析和语法分析的功能分别是什么？(4) 分析树与抽象语法树有什么不同？2. 已知字母表∑= {a, b, c}，定义在∑上的语言L具有以下特征：(5分)(1) 若出现a，则其后至少紧跟两个c；(2) 若出现b，则其后至少紧跟一个c。
试给出可以产生语言L的正规表达式。
3. 文法如下：(8分)→→→→*→ ()(1)给出句子3*)58(的最左推导；(2) 构造(1)中句子的抽象语法树。
4. 文法如下：(10分)→ ()(1) 此文法是否为二义文法？为什么？(2) 试将文法改写为非二义文法，要求运算符优先级由低到高分别是、、，且和是左结合的，是右结合的。
5. 构造题(20分) 已知正规表达式*)|((1) 使用构造方法构造对应的；(2) 用子集构造法将得到的确定化为；(3) 将得到的最小化。
6. (1)分析题(20分)文法如下：A→ P → Q →(1) 消除文法左递归，提左因子；(2) 为所得文法的每个非终结符构造集和集；(3) 所得文法是(1)文法吗？为什么？(4) 构造所得文法的(1)分析表。
7. (k)分析题(25分) 文法如下：→→→(1) 构造文法的(0)项目的；(2) 构造(1)分析表；(3) 这个文法是(1)文法吗？如果不是，请说明原因；(4) 给出对应输入串进行(1)分析的步骤(要求给出分析过程中每一步的详细情况，包括：分析栈、输出串及执行的动作)。
四川大学期末考试试题A (闭卷)(2008-2009学年第2学期)一、简答题(本大题共4小题，每小题3分，共12分)1. 按照次序写出一个完整的编译器的各个阶段以及各个阶段的输入输出。
2. 一个文法必须满足哪些条件才是(1)的？3.给出上下文无关文法( )的定义。
4.写正规表达式：所有不以0开头的十进制偶数的集合。
二、算法题(本答题共1小题，每小题8分，共8分)给出基于进行词法分析的表驱动的实现算法。
三、分析题(本答题共3小题，每小题分数见题首，共10分) 文法如下：S→*1. (4分)给出句子*的最右推导；2. (3分)构造(1)中句子的分析树；3. (3分)这个文法产生的语言是什么？四、文法二义性分析题(本大题共2小题，每小题5分，共10分)文法如下：→|()→1. 此文法是否为二义文法？为什么？2. 试将文法改写成非二义文法，要求运算符是左结合的，且的优先级高于的优先级。
五、构造题(本大题共3小题，每小题分数见题首，共20分)六、已知正规表达式()*c*b1. (6分)使用构造方法构造对应的；2. (8分)用子集构造法将得到的确定化为；3. (6分)将得到的最小化。
六、(1)分析题(本大题共4小题，每小题5分，共20分)文法如下：S→L→1. 消除文法左递归，并提左因子；2. 为所得文法的每个非终结符构造集和集；3. 构造所得文法的(1)分析表；4. 所得文法是(1)文法吗？为什么？七、(k)分析题(本大题共3小题，每小题分数见题首，共20分)文法如下：S→(A) A →B→A a b1. (10分)构造文法的(0)项目的；2. (6分)构造(1)分析表；3. (4分)这个文法是(1)文法吗？请说明是或不是的原因。
四川大学期末考试试题A (闭卷)(2007-2008学年第2学期)1. (9分)简答题(1) 编译器的前端和后端分别包括哪几个阶段？前后端分开有什么好处？(2) 在建立(1)语法分析器的时候，提左因子和消除左递归的目的分别是什么？(3) 词法分析和语法分析的功能分别是什么？2. (5分)已知字母表∑={}，定义在∑上的语言L具有以下特征：(1) 若出现a，则其后至少紧跟两个c；(2) 若出现b，则其后至少紧跟一个c。
试给出可以产生语言L的正规表达式。
3. (6分)文法如下，S→(L) L→(1)证明句子(a,())可以由此文法产生；(2) 构造(1)中句子的分析树。
4.(5分)构造如下文法的递归下降分析程序（）S→5.(10分)文法如下，→()→*(1) 此文法是否为二义文法？为什么？(2) 试将文法改写为非二义文法，其中要求运算符是左结合的，且*的优先级高于+、的优先级。
6.(20分)已知正规表达式)()*()(1)使用构造方法构造对应的；(2) 用子集构造法将得到的确定化为；(3) 将得到的最小化。
7.(25分)文法如下，S→(L) L→(1) 消除文法左递归；(2) 为所得文法的每个非终结符构造集和集；(3) 所得文法是(1)文法吗？为什么？(4) 构造所得文法的(1)分析表；(5) 写出对输入串))(,(进行(1)分析的过程。
8. (20分)文法如下，→→→(1) 构造文法的(0)项目的；(10分) (2) 构造(1)分析表；(6分)(3) 这个文法是(1)文法吗？如果不是，请说明原因；(4分) 1. 编译的各个阶段扫描程序()在这个阶段编译器实际阅读源程序（通常以字符流的形式表示）。
扫描程序执行词法分析（）：它将字符序列收集到称作记号(t o k e n）的有意义单元中，记号同自然语言，如英语中的字词相似。
语法分析程序()语法分析程序从扫描程序中获取记号形式的源代码，并完成定义程序结构的语法分析（），这与自然语言中句子的语法分析类似。
语法分析定义了程序的结构元素及其关系。
通常将语法分析的结果表示为分析树（）或语法树（）。
语义分析程序（）分析程序的静态语义，包括包括声明和类型检查。
源代码优化程序（），代码生成器（），目标代码优化程序（）2. 编译器的前端（），后端（），遍（）扫描程序、分析程序和语义分析程序是前端，代码生成器是后端。
编译器发现，在生成代码之前多次处理整个源程序很方便。
这些重复就是遍（p a s s）3. 编译器，汇编器和解释器之间的区别解释程序是如同编译器的一种语言翻译程序。
它与编译器的不同之处在于：它立即执行源程序而不是生成在翻译完成之后才执行的目标代码。
汇编程序是用于特定计算机上的汇编语言的翻译程序。
有时，编译器会生成汇编语言以作为其目标语言，然后再由一个汇编程序将它翻译成目标代码。
4. 扫描，分析（语法，词法）的任务扫描的任务是将源程序读作字符文件并将其分为若干个记号扫描程序的任务是从源代码中读取字符并形成由编译器的以后部分（通常是分析程序）处理的逻辑单元。
由扫描程序生成的逻辑单元称作记号（t o k e n）分析的任务是确定程序的语法，或称作结构分析程序的任务是从由扫描程序产生的记号中确定程序的语法结构，以及或隐式或显式地构造出表示该结构的分析树或语法树5. 上下文无关文法，最左推导，，，乔姆斯基文法层次上下文无关文法说明程序设计语言的语法结构，利用了与正则表达式中极为类似的命名惯例和运算。
二者的主要区别在于上下文无关文法的规则是递归的（）最左推导（）是指它的每一步中最左的非终结符都要被替换的推导最右推导（）则是指它的每一步中最右的非终结符都要被替换的推导。
最左推导和与其相关的分析树的内部节点的前序编号相对应；而最右推导则和后序编号相对应最左推导的一个例子：书p73相关题目：3.3中注意重复和可选的表示方法，语法图6. 句子，句型，文法所定义的语言，分析树，抽象语法树7. 自顶向下，自底向上语法分析自顶向下（t o p - d o w n）的分析算法通过在最左推导中描述出各个步骤来分析记号串输入。
之所以称这样的算法为自顶向下是由于分析树隐含的编号是一个前序编号，而且其顺序是由根到叶。
分为两类：回溯分析程序（）和预测分析程序（）自底向上的分析程序有两种可能的动作(除“接受”之外)：1) 将终结符从输入的开头移进到栈的顶部。
2) 假设有B N F选择A→a，将栈顶部的串a归约为非终结符A。
8. 为什么要解决公因子，左递归当有公因子存在时，不能立即区分出文法规则右边的选择当有左递归时，将导致一个无限循环。
9. 写正则表达式，构造，，最小化（按照算法做）构造（使用结构）: 书P45-47将转换成（最小子集法）：ε- 闭包（ε- c l o s u r e）是可由ε转换从某状态或某些状态达到的所有状态集合，它总是包含状态本身子集构造：参见(2) 相关题目：2.1，2.12，2.1610. 写最左推导，最右推导，画分析树和抽象语法树相关题目：3.311. 写出给定程序的语法树，抽象语法树相关题目：3.312. 说明文法有二义性可生成带有两个不同分析树的串的文法称作二义性文法（）相关题目：3.213. 写出给定程序的递归下降分析程序（可能用伪代码，C程序），构造语法树注意事项：在处理产生式A→ε时，可以忽略，或者使用A的集合。
不要试图去匹配ε（不然要被拉去登记的）相关题目：4.2，4.3，4.414.给定文法：消除左递归，提取公因子，求，，说明是否是(1)文法，构造(1)分析表，给出一个输入分析的动作相关题目：4.7，4.8，4.1015. 给定文法：求(0)的，构造(0)和(1)的分析表，说明是否是(0)或(1)文法（描述冲突），给定一个输入，写出(0)(1)的分析步骤相关题目：5.1，5.316. 算法（写伪代码）3种代码，(1)算法，(0)算法，(1)算法，消左递归，提公因子，构造，集合代码（英文书P63，中文P42）（1）算法（英文书P155，中文P115）（0）算法（英文书P207，中文P158）(1) 算法（英文书P210，中文P160）左递归（英文书P159，中文P119）公因子（英文书P164，中文P122）构造（英文书P168，中文P126）构造（英文书P173，中文P130）参见书本。
