CS385, Theory of Computation
Depth-First Parsing

This page is located at http://www.cs.bc.edu/~alvarez/Theory/dfparsing.html

Pseudocode for Depth-First Parsing with Backtracking

	Given a CFG G=(V,Sigma,R,S) and a terminal string w

	stack <-- empty
	candidates <-- R
	push (S,candidates)

	do {
		pop stack top into (q,candidates)
		backtracking <-- false
		do {
			write q as uAv where A is leftmost variable in q
			if target string w does not have u as a prefix
				backtracking <-- true
			if there are no A-rules in candidates
				backtracking <-- true
			if not backtracking {
				let A-->x be the first A-rule in candidates
				push (q, candidates-{A-->x})
				replace A by x in q, that is, q<--uxv
				candidates <-- R
			}
		} while not backtracking and q not terminal
	} while (q different from target string w and the stack is not empty)

	if derived string q equals target string w
		accept
	else
		reject

Infinite loops

Note carefully that the above parsing procedure may not terminate for some CFG's. This can happen if there are rules that involve recursion in the start symbol S, for example.

However, the procedure is guaranteed to terminate for any CFG expressed in what is known as "Greibach normal form", which means that each rule is of one of the following types:

A --> aA1A2...An where none of the variables Ai is the start symbol S
A --> a where a is a terminal symbol
S --> epsilon

Since any CFG may be transformed into a CFG in Greibach normal form that generates the same language, this isn't really a limitation.

Example

Find a derivation for the string aabb in the following grammar:

S --> aA | a | epsilon
A --> aA | bB | a
B --> bB | b

The search order followed by the depth-first procedure is: 

		S => aA => aaA => aaaA (backtrack)
			       => aabB => aabbB => aabbbB (backtrack)
			       			=> aabbb (backtrack)
				       => aabb (success!)