华南师范大学 编译原理期末复习整理 pdf例题

试求：

解：先消除左递归： exp → term{ addop term } addop → + | -

term → factor { mulop factor } mulop → * | /

factor → ( exp ) | number

由此得 First(exp) = { (, number }

First(term) = { (, number } First(factor) = { (, number }

例4.10 考虑if语句的文法： statement → if-stmt | other

if-stmt → if (exp) statement else-part else-part → else statement | ε exp → 0 | 1 试求： 解：

Follow(statement) = { else, $ } Follow(if-stmt) = { else, $ } Follow(else-part) = { else, $ } Follow(exp) = { ) } Follow(statement) = ? Follow(if-stmt) = ? Follow(else-part) = ? Follow(exp) = ? First(exp) = ? First(term) = ? First(factor) = ?

LL(1)分析法： 问题1: G[S] = {

S → Ab | Bc

}

A → aA | dB B → c | e

画出LL(1)分析表和当匹配串adcb时的分析栈。

解：分析表为

S A B

分析栈为：

步骤 1 2 3 4 5 6 7 8 9 问题2: G[S] = {

S → AbB | Bc A → aA | ε

S bA bAa bA bBd bB bc b 符号栈 输入串 adcb adcb adcb dcb dcb cb cb b 动作 S → Ab A → aA 匹配 A → dB 匹配 B → c 匹配 匹配 成功 a S → Ab A → aA b c d e S → Bc S → Ab S → Bc B → c A → dB B → e }

B → d | e

画出LL(1)分析表和当匹配串abd时的分析栈。

解：分析表为：

S A B

分析栈为：

步骤 1 2 3 4 5 6 7 8

S BbA BbAa BbA Bb B d 符号栈 输入串 abd abd abd bd bd d d 动作 S → AbB A → aA 匹配 A →ε 匹配 B → d 匹配 成功 a b c d S → Bc B → d e S → Bc B → e S → AbB S → AbB A → aA A → ε LR(0)分析法： 问题1： G[A]：

解：先扩充文法，得到：

A → (A) | a

画出DFA，并写出串((a))的分析过程。

A' → .A A → .(A) A → .a

DFA为：

分析表为：

输入 状态 0 1 2 3 4 5

分析串((a))时的分析栈为：

步骤 1 2 3 $0 $0(3 $0(3(3 分析栈 输入 ((a))$ (a))$ a))$ 动作 移进 移进 移进 动作 移进 规约 规约 移进 移进 规约 规则 A' → A A → a A → (A) ( 3 3 a 2 2 ) 5 Goto A 1 4