ISSN:
1432-0525
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Summary Not every unambiguous regular grammar can be parsed by a finite state machine, even if a lookahead facility is added to the machine's capabilities. Those which can be parsed with a fixed lookahead of k are said to be FL(k). If such a grammar has n non-terminals, it never needs more than (n(n−1)/2) + 1 lookahead, and there exist grammars which do require this much. An algorithm is presented for determining whether a grammar is fixed lookahead parsable, and if so, for finding the minimum lookahead needed. The algorithm sets up and solves a set of O(n2) equations using O(n4) steps. Two parsing methods for FL(k) grammars are discussed. One uses a large precomputed parsing table, and operates in real time. The second parses an input string in time proportional to its length, while using approximately 3n storage locations.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF00261256
Permalink