Regular Grammar in Compiler Design

Regular Grammar

• For notational convenience, we may wish to give names to certain regular expressions and use those names in subsequent expressions, as if the names but themselves symbols.
• Regular grammars are used for defining tokens
• The general form of regular grammar is

                        d₁ → R₁

                        d₂ →R2

                        d₃ → R₃

                        .........

                        d_n → R_n

Where d_n is a new symbol, not in Σ and not the same any other of d's and Rn is a regular expression over the alphabet Σ U{d₁,d₂,d₃......d_n-1}

Example:

Regular grammar for identifier

                        id→ letter(letter/digit)*

                        letter→A/B/..../Z/a/b/c/....z

                        digit → 0/1/2/... /9

Regular Grammar for keywords

                        if → if

                        else → else

                        then → then

Regular grammar for operators

            rel_op --> < = /</>=/>==/<>

Regular grammar for number

                        number → digits fractional_part exponential_part

                        digits → digit digit*

                        digit → 0/1/2/..../9

                        fractional_part → .digit/ε

                        exponential_part → (E(+/-/ ε)digits)/ε

Extensions of Regular Expressions

• Many extensions have been added to regular expressions to enhance their ability to specify string patterns

One or more instances(+)

Zero or one instance (?)

Character classes([])

Example:

·         Regular grammar for identifier can also be written as

                        id →letter(letter/digit)*

                        letter →[A-Z a-z]

                        digit → [0-9]

·         Regular grammar for number can also be written as

                        number → digits(.digits)?(E[+-]? digits)?

                        digits → digits*

                        digit →  [0-9]

·         Regular grammar for white space is

                        ws → (blank/tab/newline)*

Regular Expressions

Home

Recognition of Tokens