BookBody

Sec. 5.3]

Parsing with a regular grammar

111

	A	B	A	B
S	B	C	C	C	à
	a	b	c	b	a

Figure 5.8 Linearized set-based passage through the maze

5.3.1 Replacing sets by states

Although the process described above is linear in the length of the input (each next token takes an amount of work that is not dependent on the length of the input), still a lot of work has to be done for each token. What is worse, the grammar has to be consulted repeatedly and so we expect the speed of the process to depend adversely on the size of the grammar. Fortunately there is a surprising and fundamental improvement possible: from the NFA in Figure 5.6 we construct a new automaton with a new set of states, where each new state is equivalent to a set of old states. Where the original (non-deterministic) automaton was in doubt after the first a, a situation we represented as {A, B}, the new automaton firmly knows that after the first a it is in state AB.

The states of the new automaton can be constructed systematically as follows. We start with the initial state of the old automaton, which is also the initial state of the new one. For each new state we create, we examine its contents in terms of the old states, and for each token in the language we determine to which set of old states the given set leads. These sets of old states are then considered states of the new automaton. If we create the same state a second time, we do not analyse it again. This process is called the subset construction and results initially in a (deterministic) state tree. The state tree for the grammar of Figure 5.5 is depicted in Figure 5.9. To stress that it systematically checks all new states for all symbols, outgoing arcs leading nowhere are also shown. Newly generated states that have already been generated before are marked with a .

	a		a	à
	AB	b	b
a			BC
			à
b	c	a	c
S		b		AC
			BC
c		AC
		c

Figure 5.9 Deterministic state tree for the grammar of Figure 5.5

The state tree of Figure 5.9 is turned into a transition diagram by leading the arrows to states marked to their first-time representatives and removing the dead ends. The new automaton is shown in Figure 5.10. When we now use the sentence abcba as a guide for traversing this transition diagram, we find that we are never in doubt and that we safely arrive at the accepting state. All outgoing arcs from a state

112	Regular grammars and finite-state automata				[Ch. 5
			BC
			b	a
	S	a	b c	à
		AB
			c	a
			AC

Figure 5.10 Deterministic automaton for the grammar of Figure 5.5

bear different symbols, so when following a list of symbols, we are always pointed to at most one direction. If in a given state there is no outgoing arc for a given symbol, then that symbol may not occur in that position. If it is, the input is in error.

There are two things to be noted here. The first is that we see that most of the possible states of the new automaton do not actually materialize: the old automaton had 5 states, so there were 25 =32 possible states for the new automaton while in fact it has only 5; states like SB or ABC do not occur. This is usual; although there are nondeterministic finite-state automata with n states that turn into a DFA with 2n states, these are rare and have to be constructed on purpose. The average garden variety NFA with n states typically results in a DFA with less than or around 10*n states.

The second is that consulting the grammar is no longer required; the state of the automaton together with the input token fully determine the next state. To allow efficient look-up the next state can be stored in a table indexed by the old state and the input token. The table for our DFA is given in Figure 5.11.

input symbol

a b c

S AB

AB BC AC

old state
AC à BC

BC à AC

Figure 5.11 Transition table for the automaton of Figure 5.10

Using such a table, an input string can be checked at the expense of only a few machine instructions per token. For the average DFA, most of the entries in the table are empty (cannot be reached by correct input and refer to error states). Since the table can be of considerable size (300 states times 100 tokens is normal), several techniques exist to exploit the empty space by compressing the table. Dencker, Durre and Heuft [Misc 1984] give a survey of some techniques.

The parse tree obtained looks as follows:

S AB BC AC BC à

a

b

c

b

a

Sec. 5.3]

Parsing with a regular grammar

113

which is not the original parse tree. If the automaton is used only to recognize the input string this is no drawback; if the parse tree is required, it can be reconstructed in the following fairly obvious bottom-up way. Starting from the last state à and the last token a, we conclude that the last right-hand side (the “handle” in bottom-up parsing) was a. Since the state was BC, a combination of B and C, we look through the rules for B and C. We find that a derived from C->a, which narrows down BC to C. The right-most b and the C combine into the handle bC which in the set {A, C} must derive from A. Working our way backwards we find the parsing:

S	AB		BC	AC	BC	à
	. . . . . . . . . . . . . . . . . . . . . . . .				. . . . . . . .
	A		B	A	C
	a	b	c	b		a

This method again requires the grammar to be consulted repeatedly; moreover, the way back will not always be so straight as in the above example and we will have problems with ambiguous grammars. Efficient full parsing of regular grammars has received relatively little attention; substantial information can be found in Ostrand, Paull and Weyuker [FS 1981].

5.3.2 Non-standard notation

A regular grammar in standard form can only have rules of the form A ®a and A ®aB. We shall now first extend our notation with two other types of rules, A ®B and A ®e, and show how to construct NFA’s and DFA’s for them. We shall then turn to regular expressions and rules that have regular expressions as right-hand sides (for instance, P ®a * bQ) and show how to convert them into rules in the extended notation.

The grammar in Figure 5.12 contains examples of both new types of rules; Figure 5.13 presents the usual trio of NFA, state tree and DFA for this grammar. First consider the NFA. When we are in state S we see the expected transition to state B on the token a, resulting in the standard rule S->aB. The non-standard rule S->A indicates that we can get from state S to state A without reading (or producing) a symbol; we then say that we read the zero-length string e and that we make an e-transition (or e-move). The rule A->aA creates a transition from A to A marked a and B->bB does something similar. The standard rule B->b creates a transition marked b to the accepting state, and the non-standard rule A->ε creates an e-transition to the accepting state. e-transitions should not be confused with e-rules: unit rules create e-transitions to non-accepting states and e-rules create e-transitions to accepting states.

SS	->	A
S	->	a B
A	->	a A
A	->	ε
B	->	b B
B	->	b

Figure 5.12 Sample regular grammar with e-rules

114

Regular grammars and finite-state automata

[Ch. 5

		a
				a	Aà
	A
e		e		Aà
		à		a
S			ABà	b
		a		a
a		b		b
	B	SAà
				Bà
		b		b
					Bà
		b
	(a)			(b)
				a
		a	Aà
		SAà a ABà
		b	Bà

(c)b

Figure 5.13 NFA (a), state tree (b) and DFA (c) for the grammar of Figure 5.12

Now that we have constructed an NFA with e-moves, the question arises how we can process the e-moves to obtain a DFA. To answer this question we use the same reasoning as before; in Figure 5.6, after having seen an a we did not know if we were in state A or state B and we represented that as {A, B}. Here, when we enter state S, even before having processed a single symbol, we already do not know if we are in states S, A or à, since the latter two are reachable from S through e-moves. So the initial state of the DFA is already compound: SAà. We now have to consider where this state leads to for the symbols a and b. If we are in S then a will bring us to B and if we are in A, a will bring us to A. So the new state includes A and B, and since à is reachable from A through e-moves, it also includes à and its name is ABà. Continuing in this vein we can construct the complete state tree (Figure 5.13(b)) and collapse it into a DFA (c). Note that all states of the DFA contain the NFA state à, so the input may end in all of them.

The set of NFA states reachable from a given state through e-moves is called the e-closure of that state. The e-closure of, for instance, S is {S, A, à}.

5.3.3 DFA’s from regular expressions

As mentioned in Section 2.3.3, regular languages are often specified by regular expressions rather than by regular grammars. Examples of regular expressions are [0- 9]+(.[0-9]+)? which should be read as “one or more symbols from the set 0 through 9, possibly followed by a dot which must then be followed by one or more symbols from 0 through 9” (and which represents numbers with possibly a dot in them) and (ab)*(p|q)+, which should be read as “zero or more strings ab followed by one or more p’s or q’s” (and which is not directly meaningful). The usual forms occurring in regular expressions are recalled in the table in Figure 5.14; some systems provide more possibilities, some provide fewer. In computer input, no difference is generally made

Sec. 5.3]	Parsing with a regular grammar		115
Form	Meaning	Name
R 1 R 2	R 1 followed by R 2	concatenation
R 1 | R 2	R 1 or R 2	alternative
R *	zero or more R’s	optional sequence (Kleene star)
R +	one or more R’s	(proper) sequence
R ?	zero or one R	optional
(R )	R	nesting
[abc . . . ]	any symbol from the set abc . . .
a	the symbol a itself

Figure 5.14 Some usual elements of regular expressions

between the metasymbol * and the symbol *, etc. Special notations will be necessary if the language to be described contains any of the symbols | * + ? ( ) [ or ].

Rule pattern

P →a

P →aQ

P →Q

P →ε

P →a . . .

P →(R 1 | R 2 | . . . ) . . .

P →(R ) . . .

P →R * . . .

P →R + . . .

P →R ? . . .

P →[abc . . . ] . . .

replaced by:

(standard)

(standard) (extended standard) (extended standard)

P →aT

T→ . . .

P →R 1 . . .

P →R 2 . . .

. . .

P →R . . .

P →T

T→RT

T→ . . .

P →RT

T→RT

T→ . . .

P →R . . .

P → . . .

P →(a | b | c | . . . ) . . .

Figure 5.15 Transformations on regular grammars

A regular expression can be converted into a regular grammar by using the transformations given in Figure 5.15; this regular grammar can then be used to produce a DFA as described above. There is also a method to create an NFA directly from the regular expression, which requires, however, some preprocessing on the regular expression; see Thompson [FS 1968].

We shall illustrate the method using the expression (ab)*(p|q)+. Our method

116 Regular grammars and finite-state automata [Ch. 5

will also work for regular grammars that contain regular expressions (like A →ab * cB) and we shall in fact immediately turn our regular expression into such a grammar:

SS -> (ab)*(p|q)+

The T in the transformations stands for an intermediate non-terminal, to be chosen fresh for each application of a transformation; we use A, B, C . . . in the example since

that is less confusing than T 1 , T 2 , T 3 ,			. . . . The transformations are to be applied until
all rules are in (extended) standard form.
The first transformation		that	applies is P → R * . . . , which replaces
S ->(ab)*(p|q)+ by
S
SS	->	A
A	->	(ab) A
A	->	(p|q)+

The first rule is already in the desired form and has been marked . The transformations P →(R ) . . . and P →a . . . work on A->(ab)A and result in

A	->	a B
B	->	b A

Now the transformation P → R + . . . must be applied to A->(p|q)+, yielding

A	->	(p|q) C
C	->	(p|q) C
C	->	ε

The ε originated from the fact that (p|q)+ in A->(p|q)+ is not followed by anything (of which ε is a faithful representation). Now A->(p|q)C and C->(p|q)C are easily decomposed into

A	->	p C
A	->	q C
C	->	p C
C	->	q C

The complete extended-standard version can be found in Figure 5.16; an NFA and DFA can now be derived using the methods of Section 5.3.1 (not shown).

5.3.4 Fast text search using finite-state automata

Suppose we are looking for the occurrence of a short piece of text, for instance, a word or a name (the “search string”) in a large piece of text, for instance, a dictionary or an encyclopedia. One naive way of finding a search string of length n in a text would be to try to match it to the characters 1 to n; if that fails, shift the pattern one position and try to match against characters 2 to n +1, etc., until we find the search string or reach the end of the text. (Dictionaries and encyclopedias may be organized better, but a file containing a million business letters almost certainly would not.)

Sec. 5.3]	Parsing with a regular grammar			117
	SS	->	A
	A	->	a B
	B	->	b A
	A	->	p C
	A	->	q C
	C	->	p C
	C	->	q C
	C	->	ε

Figure 5.16 Extended-standard regular grammar for (ab)*(p|q)+

Finite automata offer a much more efficient way to do text search. We derive a DFA from the string, let it run down the text and when it reaches an accepting state, it has found the string. Assume for example that the search string is ababc and that the text will contain only a’s, b’s and c’s. The NFA that searches for this string is shown in Figure 5.17(a); it was derived as follows. At each character in the text there are two possibilities: either the search string starts there, which is represented by the chain of states going to the right, or it does not start there, in which case we have to skip the present character and return to the initial state. The automaton is non-deterministic, since when we see an a in state A, we have two options: to believe that it is the start of an occurrence of ababc or not to believe it.

abc

A

a

B

b

C

a

D

b

E

c

à

(a)

a

AB

a

ABD

b

b

AB

ABD

ACE

A

AB

a

a

a

c

c

AB

b

AC

b

A

A

Aà

b

a

A

c

c

c

b

A

A

A

A

A

c

A

(b)

a

a

a

a

A

a

AB

b

AC

a

ABD

b

ACE

c

Aà

c

bc

c

b

bc

bc

(c)

Figure 5.17 NFA (a), state tree (b) and DFA (c) to search for ababc

118

Regular grammars and finite-state automata

[Ch. 5

Using the traditional techniques, this NFA can be used to produce a state tree (b) and then a DFA (c). Figure 5.18 shows the states the DFA goes through when fed the text aabababca.

A AB AB AC ABDACEABDACE Aà AB

a

a

b

a

b

a

b

c

a

Figure 5.18 State transitions of the DFA of Figure 5.17(c) on aabababca

This application of finite-state automata is known as the Aho and Corasick bibliographic search algorithm [FS 1975]. Like any DFA, it requires only a few machine instructions per character. As an additional bonus it will search for several strings for the price of one. The DFA corresponding to the NFA of Figure 5.19 will search simultaneously for Kawabata, Mishima and Tanizaki; note that three different accepting states result, àK, àM and àT.

A

k

B

a

C

w

D

a

E

b

F

a

G

t

H

a à

e

K

K

K

K

K

K

K

K

K

em i s h i m a

Σ AM BM CM DM EM FM GM àM

e

t

a

n

i

z

a

k

i à

A

B

C

D

E

F

G

H

T

T

T

T

T

T

T

T

T

Figure 5.19 Example of an NDA for searching multiple strings

The Aho and Corasick algorithm is not the last word in string search; it faces stiff competition from the Rabin-Karp algorithm† and the Boyer-Moore algorithm‡ neither of which will be treated here, since they are based on different principles.

† R.M. Karp, M.O. Rabin, “Efficient randomized pattern matching algorithms”, Technical Report TR-31-81, Harvard Univ., Cambridge, Mass., 1981. We want to find a string S of length l in a text T. First we choose a hash function H that assigns a large integer to any string of length l and calculate H (S) and H (T [1..l ]). If they are equal, we compare S and T [1..l ]. If either fails

we calculate H (T [2..l +1]) and repeat the	process. The trick is	to choose	H so that
H (T [p +1..p +l ]) can be calculated cheaply	from H (T [p..p +l −1]).	See also	Sedgewick
[CSBooks 1988], page 289.

‡ Robert S. Boyer, J. Strother Moore, “A fast string searching algorithm”, Commun. ACM, vol. 20, no. 10, p. 762-772, Oct 1977. We want to find a string S of length l in a text T and start by positioning S [1] at T [1]. Now suppose that T [l ] does not occur in S; then we can shift S to T [l +1] without missing a match, and thus increase the speed of the search process. This principle can be extended to blocks of more characters. See also Sedgewick [CSBooks 1988], page 286.

6

General directional top-down methods

In this chapter, we will discuss top-down parsing methods that try to rederive the input sentence by prediction. As explained in Section 3.3.1, we start with the start symbol and try to produce the input from it. At any point in time, we have a sentential form that represents our prediction of the rest of the input sentence:

rest of input

prediction

This sentential form consists of both terminals and non-terminals. If a terminal symbol is in front, we match it with the current input symbol. If a non-terminal is in front, we pick one of its right-hand sides and replace the non-terminal with this right-hand side. This way, we all the time replace the left-most non-terminal, and in the end, if we succeed, we have imitated a left-most production.

6.1 IMITATING LEFT-MOST PRODUCTIONS

Let us see how such a rederiving process could proceed with an example. Consider the example grammar of Figure 6.1. This grammar produces all sentences with equal numbers of a’s and b’s.

S -> aB | bA

A-> a | aS | bAA

B-> b | bS | aBB

Figure 6.1 A grammar producing all sentences with equal numbers of a’s and b’s

Let us try to parse the sentence aabb, by trying to rederive it from the start-symbol, S. S is our first prediction. The first symbol of our prediction is a non-terminal, so we have to replace it by one of its right-hand sides. In this grammar, there are two choices for S: either we use the rule S->aB, or we use the rule S->bA. The sentence starts with an a and not with a b, so we cannot use the second rule here. Applying the first rule

120

General directional top-down methods

[Ch. 6

leaves us with the prediction aB. Now, the first symbol of the prediction is a terminal symbol. Here, we have no choice:

a abb

a B

We have to match this symbol with the current symbol of the sentence, which is also an a. So, we have a match, and accept the a. This leaves us with the prediction B for the rest of the sentence: abb. The first symbol of the prediction is again a non-terminal, so it has to be replaced by one of its right-hand sides. Now, we have three choices. However, the first and the second are not applicable here, because they start with a b, and we need another a. Therefore, we take the third choice, so now we have prediction aBB:

a a bb

a a BB

Again, we have a match with the current input symbol, so we accept it and continue with the prediction BB for bb. Again, we have to replace the left-most B by one of its choices. The next terminal in the sentence is a b, so the third choice is not applicable here. This still leaves us with two choices, b and bS. So, we can either try them both, or be a bit more intelligent about it. If we would take bS, then we would get at least another a (because of the S), so this cannot be the right choice. So, we take the b choice, and get the prediction bB for bb. Again, we have a match, and this leaves us with prediction B for b. For the same reason, we take the b choice again. After matching, this leaves us with an empty prediction. Luckily, we are also at the end of the input sentence, so we accept it. If we had made notes of the production rules used, we would have found the following derivation:

S -> aB -> aaBB -> aabB -> aabb.

Figure 6.2 presents the steps of the parse in a tree-form. The dashed line separates the already processed part from the prediction. All the time, the left-most symbol of the prediction is processed.

This example demonstrates several aspects that the parsers discussed in this chapter have in common:

we always process the left-most symbol of the prediction;

if this symbol is a terminal, we have no choice: we have to match it with the current input symbol or reject the parse;

if this symbol is a non-terminal, we have to make a prediction: it has to be replaced by one of its right-hand sides. Thus, we always process the left-most non-terminal first, so we get a left-most derivation.