语法分析自顶向下分析课后作业.doc

课后作业 —— 语法分析--自顶向下分析 基本要求 2型文法的概念和自顶向下分析的分析思想。 熟练掌握推导、FIRST集和FOLLOW集、消除左递归、提取左因子、LL(1)文法、文法的改写、递归子程序法、预测分析法。 了解文法的二义性。 习题 1. (1)?M → M a H? |? H H → b ( M )? |? ( M )? |? b (2)S → S b | A b | b A → A a | a ? 2. 改写以下文法，消除文法中的左递归并提取左因子。 S→ aXcY | Yd X → XaY | c Y → bYcX | b ? 3. 求以下文法中的各候选式的FIRST集和各非终结符的FOLLOW集 A → b a B | e B → A b b | a ? 4.?考虑文法G[S]： S → xSNy| Nx N → zN|ε (1)?求该文法的每个非终结符的FOLLOW集; (2)?判断该文法是否为LL(1)文法； (3)?构造该文法的预测分析表。?? 第一页 课后作业 —— 语法分析--自顶向下分析 5.G[S]： S → ?id? L ?; L → ?L? ， a ??|? ?:? a （1） （2）按照改写后的文法画出并化简语法图。 ? 6.?判断下述文法是否可改写为 LL(1)文法，若可以，则给出改写后文法及改写后文法的预测分析表。 1)?S→ A | B A→ aA | a B→ bB | b 2)?S→ id | ( E ) E→E + S | E-S | S 3)?S → A B A → B a | e B → D b | D D → d | e 4)?S → T | T [ E ] E → S | S + E T → ?id ? 7.?给出文法 G[S]，按照递归子程序法构造相应的处理程序 S → a | ^ | ( T ) T → T , S | S ? 8. 简述在给定一个上下文无关文法的条件下，采用递归子程序方法设计一个语法分析程序的过程由哪些步骤组成。 第二页 课后作业 —— 语法分析--自顶向下分析 9. 1)?能否直接用语法图描述对如下文法的分析？能否递归子程序法实现语法分析？为什么？ E → E + T |? E - T | T T → T * F |? T / F | F F → ( E ) | id | const 2) 能否将各种单词的文法直接并入表达式语法，在进行语法分析处理的同时完成词法分析？试对这种做法进行分析。 10.上机题 构造下列文法的语法分析器： S→id=E S→if C then S S→if C then S else S S→while C do S C→EE C→E=E C→EE E → E + T E → E - T E → T T → T * F T → T / F T → F F → ( E ) F →id F →int8 F →int10 F →int16