Name
Abstract | ||
|---|---|---|
This paper is devoted to the presentation of a two-parameter family M
k
t
of parsers for general context-free grammars ; the algorithms have a top-down structure, in which all the possible candidate parses are investigated in parallel. Backtracking is avoided by keeping track of the stage reached in all parses in a set of "states". The integer parameters t and k describe tests performed on strings of terminals, of length t and k respectively, to the right of the point currently reached in the analysis of an input string. The tests involving parameter k enhance the performance of the parser on grammars with LR(k) characteristics, whereas those involving parameter t are most suited for grammars showing LL(t)-type conditions. However, the use of parallelism enables the algorithm to work on any CF-grammar.
Extensive comparison is made between the M
k
t
parsers and algorithms proposed by Earley | 3,4 | which are the M
k
o
members of the M
k
t
family.
Theoretical comparisons are made on time bounds. It is shown that M
k
t
is always at least as good as M
k
o
. When M
k
t
recognizes a string of length n as a sentence of some grammar G, then the time needed by the algorithm is at most proportional to n3. Time is proportional to n2 for unambiguous grammars and linear grammars and proportional to n for LR(k) grammars. It is also proved that M
o
t
performs at most in time n for LR(t) and LL(t) grammars.
Extensive experimental comparisons show a definite superiority in time performances for M
o
l
over M
o
o
, M
l
o
and M
l
l
, especially on large grammars which correspond to realistic examples. Only a single, very peculiar, example was found for M
l
o
is better (i.e. takes less time) than M
o
l
, but it is sufficient to preclude the possibility of discovering stronger theoretical results which would express the superiority of M
o
t
.
In practice, as a parser for general context-free grammars, M
o
l
was found much more efficient than Earley's parser and it is used as the syntactic component of a general compiling system built in our laboratory (Bouckaert et al. |1|).
|
Year | DOI | Venue |
|---|---|---|
1973 | 10.1007/3-540-06473-7_10 | GI Jahrestagung |
Keywords | Field | DocType |
context-free parser,top down,context free grammar | Integer,Rule-based machine translation,Top-down parsing,Programming language,Computer science,Simple LR parser,Operator-precedence grammar,GLR parser,Parsing,Backtracking | Conference |
ISBN | Citations | PageRank |
3-540-06473-7 | 2 | 0.92 |
References | Authors | |
1 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| M. Bouckaert | 1 | 12 | 3.81 |
| Alain Pirotte | 2 | 916 | 260.52 |
| M. Snelling | 3 | 2 | 0.92 |