I'm opening a new series of updates to v-parser under project "Esperas". Firstly, the algorithm is a bit cleaned up:
01 DECLARE chart: [][], text: STRING;
02
03 FUNCTION Parse (grammar, input)
04 text ↠input;
05 chart.CLEAR ();
06 MergeItem (0, [grammar.START_SEQUENCE], 0, null);
07 FOR each new column in chart DO
08 FOR each new item in column DO
09 FOR each production of item.Sequence[item.Index] in grammar DO
10 MergeItem (column.Index, production.sequence, 0, item);
11
12 RETURN chart;
13
14 PROCEDURE MergeItem (offset, sequence, index, parent)
15 item ↠chart[offset].FIND (sequence, index);
16 IF not found item THEN
17 item ↠{Sequence: sequence, Index: index, Inherited: [], Inheritors: [], Parents: []};
18 chart[offset].ADD (item);
19
20 IF parent not in item.Parents THEN
21 item.Parents.ADD (parent);
22 FOR each x in [parent] UNION parent.Inherited DO
23 IF x.Index + 1 < x.Sequence.LENGTH THEN
24 FOR each y in [item] UNION item.Inheritors DO
25 IF y.Index + 1 == y.Sequence.LENGTH OR y is terminal THEN
26 IF (x.Sequence, x.Index) not in y.Inherited THEN
27 x.Inheritors.ADD (y);
28 y.Inherited.ADD (x);
29
30 IF y is terminal succeeded in text at offset THEN
31 FOR each z in x.Parents DO
32 MergeItem (offset + y.LENGTH, x.Sequence, x.Index + 1, z);
Secondly, Javascript implementation is simplified to the bones. I removed all unnecessary grammar tree processing, and the implementation now takes about 170 lines of code, taking a kind of context free grammar as a part of an input. Also, documentation finally started to shape up in some decent manner.
In incoming weeks I plan to extend the parser first to a "syntax logic" parser, then to a full Turing complete parser, but not incorporating
unrestricted grammar, as proposed in mainstream textbooks. Because of their nature, with unrestricted grammar it is mostly impossible to build up an abstract syntax tree that grows from only one parent trunk, so the output is pretty messy and hard to cope with. Instead, I decided to use my own thought-child which I call "grammar templates". "Grammar templates" will behave somewhat like classic functions (we can trigger parametric productions) and will have strict parent-child branching from only one parent trunk, while providing Turing completeness wired into grammars. The final version will serve as a jumping board for meta-theory
"Logos" language which I have written about here a while ago.
The first whole of Esperas is already on Github. One down, two more to go, wish me luck
Read about it
here, and test the algorithm
here.