Scanners (Compiler Writing) Part 2

REGULAR GRAMMARS AND REGULAR EXPRESSIONS

In Sec. 2-3, the grammar classification of Chomsky was introduced. In this section, one class of these grammars, the 7"3 or regular grammars, is discussed. Regular expressions are also described in this section, and an algorithm for converting a regular grammar to a regular expression is given. Both formalisms can be used to describe tokens.

Recall from topic 2 that a regular grammar is defined to consist only of productions of the formhas the form aB or a whereFurthermore, the languages generated by such grammars are said to be regular. Examples of regular grammars and regular languages were presented in Chap. 2.

A more compact way of representing regular languages is with the use of regular expressions. The equivalence of regular grammars and regular expressions will be demonstrated in the next two sections when proofs of the equivalence of regular grammars and finite-state acceptors and of regular expressions and finite-state acceptors are given.

Regular expressions make use of three operators: concatenation, alternation, and closure. Assume that the two expressions ei and e2 generate the languages and L2, respectively. Concatenation is then defined asand Alternation, which is denoted by either | or +, is the union of the languages denoted by two expressions. Hence,

Closure, which is represented by the braces { }, denotes the repetition of the expression zero or more times. Thus,

These operators are analogous to the BNF operators introduced in Chap. 2. For example, the expression 110 consists of the digits 1, 1, and 0 concatenated together and denotes the language L = {110}. The expression 0|1 denotes the language L = {0,1} while the expression {1} denotes the language L = |1′| / = 0,1,2,…}.

Other examples of regular expressions that specify familiar sets of tokens follow.

Note that the terms letter and digit represent the sets of alphabetic letters and decimal digits, respectively.

Using the definitions of the above operators, a formal definition of regular expressions is now given.

Definition 4-1 Regular expressions are those expressions that can be constructed from the following rules:

1. $ is a regular expression denoting the empty set.

2. e is a regular expression denoting the language consisting of only the empty string, that is, {e}.

3. a, whereis a regular expression denoting the language consisting of the single symbol a, that is, the language {a}.

4. If el and e2 are regular expressions denoting the languages Lx and L2, respectively, then:

(a)is a regular expression denoting

(b)is a regular expression denoting .(c)is a regular expression denoting

If the precedence of the operators in regular expressions are defined with closure ({ }) having the highest precedence, concatenation with the next highest, and alternation (|) having the lowest precedence, the parentheses can be eliminated whenever possible. Thus, ((/?)!((/>)(?))) would have the same meaning if the parentheses were omitted. In the case of {p\q)r, the parentheses cannot be removed, as the language denoted by the expression would become different.

Some examples of regular expressions are now given. The expression {a} {b} represents the languageThis expression can be compared with the expression {ab} which generates the languageand the expression {a\b} denoting the languageThe expression {aa\ab\ba\bb} denotes all strings overof even length. This can be seen by observing that the expression aa\ab\ba\bb denotes all strings of length two with zero or more combinations of the strings generated by this expression producing strings all of an even length.

It is convenient to define the equality of regular expressions. Two regular expressions are equal (=) or equivalent if they denote the same language. Thus, 0(0} = 00(0} 10 as each expression generates the language

The tokens of a programming language can be defined in terms of regular grammars and regular expressions. For example, an identifier which consists of letters and digits and must begin with a letter can be described by the regular grammar

and by the regular expression

Using letter as a shorthand representation for a \ b \ c| … |z and digit for 0111 … 19, the expression might be written as letter{letter| digit} to improve readability. As we shall see in Sec. 4-7, regular expressions are often used to describe tokens for a scanner generator.

For the remainder of this section, a method for converting regular grammars to regular expressions is presented. At this point, however, it should be noted that the regular-expression operators obey some algebraic rules. For example, both alternation and concatenation are associative, with alternation also being commutative. Thus we can write (ab)c = a(bc), (a\b)\c = a\(b\c), and a\b = b\a. Distributivity also applies, with concatenation distributing over alternation; that is, a{b\c) = ab\ac. Proofs of these identities are left as exercises. Finally, regular expressions can be used in equations and therefore evaluated. For example, A = {aA} is a valid regular-expression equation.

To present a method of converting a regular grammar to a regular expression, consider the following regular grammar from Chap. 2 which generates the language

Replacing the production operator (-») with an equal sign and combining all possible productions from a given nonterminal into one expression by using the alternation operator, the grammar can be written as the set of equations

By solving this set of equations, a regular expression with only terminal symbols is derived which generates the same language as the original regular grammar. Solutions for equations which are defined only in terms of themselves should be done first. In this example, the equation for C has a solution of C = {a}a. This can be shown by substituting this solution into the equation for C, giving

Factoring yields

Now,, since e is in both sides of the equation, a is in both sides, and any string a’ is in both sides.

The solution for C can be substituted into the second equation, and the third equation can be dropped as it is no longer needed. This results in the set of equations

We immediately have a solution for B which can be substituted into the first equation. This results in the equation

It can easily be shown that a solution for S is S = {a}ab{a}a, which is a regular expression generating the same language as the original regular grammar.

An algorithm which generates an equivalent regular expression from a regular grammar is now given.

Algorithm REGULAFLEXPRESSION. Given a regular grammar with the set of productions of the formis of the form aXj or a where this algorithm generates an equivalent regular expression. Xl is the starting symbol of the grammar and there are n terminal symbols in the grammar.

1. [Convert the regular expression equations]

Repeat for each productionof the regular grammar

If the equation X, has not been initialized then Define else Changewhere a is the previously defined part of the equation X,

2. [Convert equations to required format]

Repeat for /’ = 1,2,…,n – 1

Convert equation X, into the formwhere is of the formand a, and eachis a regular expression over Repeat for

Substitute

3. [Solve for the solution]

Repeat for /’ = n,n – 1…..1

Convert the equation for X, into the formwhereis a regular expression over Repeat for j = i – 1, i – 2,…,1 Substitute the solutioninto the equation for Xt

Step 2 then converts each equation to the form

While some algebraic manipulation may be required, it is possible for each equation to be converted to this form. Step 3 uses back substitution to solve the set of equations. The solution for Xn is easily found, as this equation has the form and it isThis solution is then substituted into each preceding equation. Once a solution for equation X, has been found and substituted into the preceding equations, the equation forhas only the unknownin it, and the equation can be written in the form

Thus a solution foris easily computed. At the completion of step 3, the regular expression for X1 is the regular expression equivalent to the regular grammar which the algorithm started with. A trace of this algorithm is left for the exercises.

In the next section, finite-state acceptors are introduced. Finite-state acceptors are theoretical machines which can be used to determine whether a given string can be generated from a regular grammar or a regular expression. In closing, a scanner generator based on regular expressions is discussed in Sec. 4-7.

FINITE-STATE ACCEPTORS

In this section we continue the discussion of finite-state acceptors introduced in Sec. 4-2. Scanner generators often create a scanner which simulates a finite-state acceptor, as it is not difficult to program an acceptor on a computer. Three types of finite-state acceptors are examined: deterministic, nondeterministic, and non-deterministic with e-transitions. The equivalence of these types of acceptors is also demonstrated.

Deterministic Finite-State Acceptors

A deterministic finite-state acceptor (DFA), which is also known as a deterministic finite automaton, is an acceptor which for any state and input character has at most one transition state that the acceptor changes to. If no transition state is specified, the input string is rejected.

The following definition formally introduces a DFA.

Definition 4-2 A deterministic finite-state acceptor (DFA) is a 5-tuple (K, VT, M, S, Z) where:

K is a finite, nonempty set of elements called states. VT is an alphabet called the input alphabet. M is a mapping from K X VT into K.

is called the initial state or starting state. is a nonempty set of final states.

The DFA is initially in state 5 and reads an input string from left to right. The mapping function M of the DFA defines the state transitions and is denoted by M(Q, T) = R, where Q and R are states of K and T is a character from the input alphabet. The mapping function indicates that when the acceptor is in state Q and T is the next input character, the acceptor changes to state R. The following two definitions complete the specification of the mapping function:

The first definition implies that a DFA cannot change state without reading a character from .the input alphabet, while the second definition is a recursive definition showing that when the DFA is in state Q with some input string x = Tt, the mapping M(Q, T) is applied first with the result P = M(Q, T). Then the mapping M(P, t) can be applied. This definition extends the applicability of the mapping function to strings over rather than just elements of VT.

A sentence t is said to be accepted by a DFA if M(S, t) = P for some DFA F = (K, VT, M,S,Z) such thatandThe string t is accepted by the DFA if, after reading the entire string, the DFA terminates in a final state. The set of all t e V* which is accepted by the DFA F is specified by L{F). Thus L(F) is defined as

Figure 4-5 An example of a deterministic finite-state acceptor.

The following DFA is an example of an acceptor which accepts strings consisting only of an even number of Os and an even number of Is.

where M is defined as

The transition diagram for this acceptor is given in Fig. 4-5.

The mapping function for an acceptor is sometimes more conveniently illustrated with a transition table such as Table 4-1, which defines M in the previous example.

An example of a string which is accepted by this DFA is 110101, and a string not accepted is 11101. Traces of the DFA operating on these strings are given in Table 4-2.

In this subsection, deterministic finite-state acceptors were discussed. The next subsection examines finite-state acceptors which may have more than one transition for a given state and input character. Such an acceptor is shown to be no more powerful than its deterministic counterpart.