Re: Generating a simple hand-coded like recursive descent parser

oliverhunt@gmail.com wrote:
> Mr.E wrote:
> > There are approximately 600 keyword or keyword combinations which
> > include compound words due to intrinsic functions.
>
> What do you mean by keyword combinations?


Examples off the top of my head


keyword or compound phase, usage
"compile", directive on what compiler options will be used
"compile long if", conditional compile block statement
"compile xelse", what to do if the conditional compile expression fails
"compile end if", end of conditially compiled block
"clear", reinitialize global and main scoped variables for entire
program
"clear local", initialize variables belonging to function before use
"clear local mode" , same as "clear local" but user global variable are
inaccessible ( not visible to the function)
"local", indicates start of local variables scope
"local mode", start of local scope, procedure can not see global
variables
"def fn <function name> [( paramater list)]", prototype a function
"def fn <function name> = expression", simple function
"def fn <function name> USING functionPointer", virtual function
prototype


> > Is there a parser generator that produces the equivalent of a
> > hand-coded recursive descent parser? I'm looking for a generator
> > that doesn't require an engine and doesn't use external libraries...
> > just plain old C.
>
> I've seen CoCo/R mentioned... ANTLR also produces recursive descent
> (LL(*)) parsers, but converting its output to basic may be about the
> least fun thing you could do...


I will check out CoCo/R.


> > I can watch and debug recursive descent code because I can understand
> > that. I cant imagine trying to debug a table driven parser or having
> > to rewrite it in BASIC.
>
> You could always write one by hand -- BASIC's grammar isn't overly
> complex, and it could be a good learning experience :D


I thought it would be character building and and I am finding it
humbling :-)


> > Also are there any algorithms for AST building. Everything I've
> > understand tells me that I really want to build an AST and do code
> > generation from it versus trying to generate code as I go along. I
> > thought I understood the process but I'm not there yet.
>
> Well that one's up to you... you could make a completely abstract tree:
> struct ASTNode {
> int isLeaf;
> void *leaf;
> struct {
> int numChildren;
> ASTNode *children;
> } branch;
> }
>
> In this you can just store the whole parse tree, alternatively you just
> store the semantics of what is being parsed. In which case basically
> all you are doing is building a tree that represents the important bits
> of your grammar. eg (from http://en.wikipedia.org/wiki/Tiny_BASIC -- i
> really don't know basic :D).
> statement ::= PRINT expr-list
> IF expression relop expression THEN statement
> GOTO expression
> INPUT var-list
> LET var = expression
> GOSUB expression
> RETURN
> CLEAR
> LIST
> RUN
> END
>
> for which you *might* make a pair of types:
> enum statement_type {
> print_statement, if_statement, goto_statement, ..., end_statement
> };
>
> struct statement_s {
> statement_type type;
> union {
> struct {
> expression_list *expressions;
> } print_stat;
> struct {
> relop operator;
> expression *lhs, *rhs;
> struct statement_s *statement;
> } if_stat;
> struct {
> expression *target;
> } goto_statement;
> ...
> };
> };
>
>
> Now when you parse a statement you create a statement struct for the
> appropriate branch, and fill in the appropriate bits. But note we
> aren't storing syntax info -- all we have in the node is the actual
> information we *need* to reconstruct the meaning.
>
> Apologies for any issues in the above codei tend to use languages where
> subtyping is an option :D
>
> And other people here can probably explain this somewhat better than i
> have :(
>
> --Oliver


I've been trying to follow the AST of the LCC compiler ( I own Hanson &
Frasier's book). The idea behind creating DAG's is good, but maybe
problematic for me. I'm not willing to use code or ideas I dont fully
comprehend. The first time it breaks or something near it breaks is
when your in trouble.


> Apologies for any issues in the above codei tend to use languages where
> subtyping is an option :D


No need to apologize. You explained it the way you know how with an
example. Its up to me now to take it in.


Thank you for your assistance,




W.

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