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. A greedy regex would also have to check all
successor options (C in the exapmle above) to determine the
longest one.
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.
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).
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.
