# 编译原理作业4

## Exercise 4.1

Given the following grammar ：
$$S → ( L ) | a\ L → L , S | S$$

• Eliminate left recursions in the grammar.

• Draw the transition diagrams for the grammar.

• Write a recursive descent predictive parser.

• Indicate the procedure call sequence for an input sentence (a, (a, a)).

$$S → ( L ) | a\ L → SL’\ L’ → ,SL’ | \epsilon$$

recursive descent predictive parser如下：

## Exercise 4.2

Consider the context-free grammar

$$S → a \ S\ b\ S\ |\ b\ S\ a\ S\ |\ \epsilon$$

Can you construct a predictive parser for the grammar? and why?

$FIRST(\alpha) = {a,b}$,$FOLLOW(S) = {a,b, \psi}$

$FIRST(\alpha)\ \cap \ FOLLOW(S) \neq \varnothing$

## Exercise 4.3

Compute the FIRST and FOLLOW for the start symbol of the following grammar.
$$S → \ S\ S\ +\ |\ S\ S\ *\ |\ a$$
$FIRST(S) = {a}$

$FOLLOW(S) = {+, * , \psi}$