Assignment Week4-1

(1) 无左递归、无回溯

(2) 左递归会在匹配时无限循环自身到自身的匹配，无法进行分析；其他递归会在输入匹配部分字符后再进行递归，故不会死循环

去掉左递归：

A ::= (B) | dBe

B ::= c{c}


procedure A:
Begin
	if getch = '('
		B()
		if getch = ')'
			output('A')
		else
			error
	else if getch = 'd'
		B()
		if getch = 'e'
			output('A')
		else
			error
	else
		error		
End	

procedure B:
Begin
	if getch = 'c'
		while getch = 'c';
		output('B')
	else
		error	
End

(1) FIRST(AcB) = {c}

FIRST(Bd) = {a}

FIRST(AaB) = {c}

FIRST(c) = {c}

FIRST(aA) = {a}

FIRST(a) = {a}

FIRST (A) = {c}

FIRST (B) = {a}

FIRST(Z)=FIRST(A)∪FIRST(B)={a,c}

(2) 不能，有左递归文法

(3) 改写后：

Z ::=AcB | Bd

A ::= cA’

A’ ::= aB | ε

B ::= aA | a


procedure Z:
BEGIN
	if A(getSym)
		if getSym = c
			if B(getSym)
				output('Z')
			else
				error
		else
			error
	else if B(getSym)
		if getSym = d
			output('Z')
		else 
			error
	else
		error	
END

procedure A:
BEGIN
	if getSym = c
		if A'(getSym)
			output('A')
		else
			error
	else
		error		
END

procedure A':
BEGIN
	if getSym = a
		if B(getSym)
			output('A\'')
		else
			ungetSym;
			ungetSym;
			output('A\'')
	else
		ungetSym;
		output('A\'')
END

procedure B:
BEGIN
	if getSym = a
		if A(getSym)
			output('B')
	output('B')				
END