On 08-Jul-12 01:49, Roman D. Boiko wrote:
On Saturday, 7 July 2012 at 21:35:52 UTC, Dmitry Olshansky wrote:
On 08-Jul-12 01:24, Roman D. Boiko wrote:
But PEG itself doesn't require backtracking parsing, does it?
It does. Specifically the algorithm is to try option A, try option B,
try option C...
There is no algorithm, only __grammar__. It specifies that option A has
higher priority than option B in expression A / B / C. But it doesn't
forbid, for example, to analyze all in parallel (track state
transitions) for each character consequently, as a proper DFA
implementation would do, until some option succeeds and all previous
fail.
That would not always work, but yes that's what we should do IMHO.
It's not what packrats do however (when I say algorithm I mean
specifically packrat). And PEGs are commonly associated with packrats.
A greedy regex would also have to check all successor options (C
in the exapmle above) to determine the longest one.
Yes, yet regex engine (in simple form) can 'merge' identical parallel
states* easily it's not so simple with general CFGs.
*As in NFA states, I like to think in multiple NFA states vs single DFA
state.
it's obvious how backtracking comes in ... whan say A fails somewhere
in the middle of it.
Simply stop tracking respective state. Process others in parallel as I
described above.
Yeah it could be done, but it doesn't buy you a thing in a lot of cases
unlike in regular grammar. The problem is that state is not as simple as
in regex for instance (even in regex that must capture some submatches
DFA won't do BTW). Thus you can't merge seemingly identical states
because they depend on (different) interpretation of previous part of
input.
That's why DFA in ANTLR is only used to do lookahead or lexing, it
doesn't maintain path through states during parsing.
Of course there is a fair amount of bookkeeping that reduces doing
work all over again but it does ... allocate.
The amount of used memory would be proportional to the length of input
after the branching point times number of rules (actually, of states in
the DFA, which is likely larger but still finite for a particular grammar).
Finite and proportional to input size? Another way to say why an O(n)
memory requirement for packrats?
Tokens.. there is no such term in use if we talk about 'pure' PEG.
Terminal symbols.
Characters.
Nope. According to the definition, PEG is a set of non-terminal symbols,
terminal symbols, production rules, and a starting non-terminal.
Terminals are not necessarily characters.
Yup. But I'm not talking definitions here I'm talking the notion of
"integrated lexing" and lexing is certainly about characters or was it?
--
Dmitry Olshansky
