SkipCaptcha
265
edits
Changes
Jump to navigation
Jump to search
Line 160:
Line 160: − This example of a regular grammar shows how a ''Word'' can be defined as a sequence of ''Letter''s.+ + + + + − In its simplest form a ''Word'' consists of a sequence of one or more letters. In the regular grammar which follows the two possible transformations of ''PartWord'' are placed on separate lines instead of on one line separated by a comma. We ignore capital letters for now. ''PartWord'' is recursively defined and may be transformed into [nothing].+ + Line 168:
Line 173: + + Line 175:
Line 182: − + + + + − +
→Level 3: regular grammar: explain restrictions on rules more carefully; add subheadings
===Level 3: regular grammar===
===Level 3: regular grammar===
The transformation rules for regular grammars are required to be very simple. The right-hand side of any rule must be one of:
* [nothing].
* a terminal item.
* a terminal item followed by a non-terminal item.
Note that instead of a terminal item we could have a non-terminal item whose transformation rule immediately resolves to a single terminal item.
====Example====
Informally we can define a 'word' as a sequence of one or more ''Letter''s. The following regular grammar provides a more formal definition; for simplicity it is restricted to lower-case letters.
''Word'' -> ''Letter'' ''PartWord''
''Word'' -> ''Letter'' ''PartWord''
''PartWord'' -> ''Letter'' ''PartWord''
''PartWord'' -> ''Letter'' ''PartWord''
''Letter'' -> '''a''', '''b''', ... '''z'''
''Letter'' -> '''a''', '''b''', ... '''z'''
Note that ''PartWord'' is recursively defined, with the recursion stopping if it is transformed into [nothing].
For one-letter words we expand as:
For one-letter words we expand as:
:''Word'' -> ''Letter'' ''PartWord'' -> ''Letter'' ''Letter'' ''PartWord'' -> ''Letter'' ''Letter'' [nothing] -> ''Letter'' ''Letter''
:''Word'' -> ''Letter'' ''PartWord'' -> ''Letter'' ''Letter'' ''PartWord'' -> ''Letter'' ''Letter'' [nothing] -> ''Letter'' ''Letter''
Obviously, words of any length can be constructed. Trying to further constrain the productions to produce words which are more English-like is much more difficult - how do you insist on at least one vowel or on no more than 5 consecutive consonants (e.g. as in 'strengths').
Obviously, words of any length can be constructed, though they may well not actually be words from any language.
====Discussion====
Trying to devise transformation rules to produce words which are more English-like is much more difficult - how do you insist on at least one vowel or on no more than 5 consecutive consonants (e.g. as in 'strengths').
Further examples in [[Regular grammar]] show how numbers can be defined via a regular grammar, and also show how a hyphenated word could be defined.
Further examples in [[Regular grammar]] show how numbers can be defined via a regular grammar, and also show how a hyphenated word could be defined.
One of the limitations of a regular grammar is that it can't cope with nested matching brackets, so that it is impossible to write a regular grammar to describe a simple expression such as '''2 * (3+4)''' where that grammar is expected to allow brackets nested to any depth.
One of the limitations of a regular grammar is that it can't cope with nested matching brackets, so that it is impossible to write a regular grammar to describe an expression such as '''2 * (3+4)''' where that grammar is expected to allow brackets nested to any depth. A context-free grammar is needed for this, as described in the next section.
Regular grammars or equivalent are widely used during [[compilation]] in the lexical analysis of programming languages.
Regular grammars or equivalent are widely used during [[compilation]] in the lexical analysis of programming languages.