Re: Suggestion for dynamic grammar/parser - pls advise

> My thought is that implementing a parser based on a dynamic
> grammar/parser scheme is the answer (I am not an expert on compiler
> design or theory). If so, there appear to be many different types of
> dynamic grammar and parsing schemes. I am hoping someone with much more
> experience in the compiler design/theory area can point me in the right
> direction.


I think you are right, the solution is to use dymamic methods of
parsing to implement yor task on the best way. My dissertation thesis
were about this task. I also had the language, which could be extended
by new productions, terminals and nonterminals between two runs of
parsing algorithm. And the first task was to select the best parsing
method for such dynamic parsing. After some review of parsing methods
I had selected Earley.s algorithm to implement. It is very simple
method - some kind of dynamic programming paradigma. The problem was
the algorithm can went into nonterminated loop for some specific
productions and when the parser trying to build Chomsky's trees (the
syntax trees for the parsing of this terminal string) during the work
of the parsing algorithm. That was the reason why Tomita selected
nondeterminate LR(k) analyser to implement his parser of a natural
language. I had changed the algorithm to work correctly with any kind
of grammar and build syntax tree exactly in time the syntax analysis
doing. I've already described this idea simething in this conference,
so you can easy find this by entering Earley word in the search field.
The other problem was how to extend terminals' set? I represent each
terminal as the regular language, so it could be implemented by finite
state machine or described by an regular expression. For instance, c++
language's ID terminal is the regular language (the set of strings) (_|
(a-z)|(A-Z)(_|(a-z)|(A-Z)|()0-9). It can be easy implemented by
determinated finite automata (DFA). I built the program, which allowed
to add terminals to the grammar by describibg them by the regular
expression (RE). Then this RE had been translated to DFA and saved in
the parser. When the lexical analysis was needed to be done the parser
called each of terminalss DFAs for each symbol of the input text and
found the DFA, which went through the longest string while been in the
finite state. So, the process is something like laze evaluation of DFA
from NFA by doing dynamically. Thus, the parser found the terminal
string in the text and returned the terminal as the type of the
string. The problem also was how to build abstarct syntax tree from
the syntax trees (treeS - is it was some ambiguty during the parsing).
I hooked spesial function to each new production to build this portion
of the anstract tree from the syntax tree for this production. The
work likes to be big (and from now I think it is big enough), but the
parser is not to hard to implement, not hardly then LR(k) for example.

Return to the comp.compilers page.
Search the comp.compilers archives again.