Making a CFG for RDP with one token lookahead.

Rasmus Anthin <e8rasmus@etek.chalmers.se>
22 Jun 2000 01:43:11 -0400

          From comp.compilers

Related articles
Making a CFG for RDP with one token lookahead. e8rasmus@etek.chalmers.se (Rasmus Anthin) (2000-06-22)
Re: Making a CFG for RDP with one token lookahead. feriozi@my-deja.com (2000-06-30)
| List of all articles for this month |

From: Rasmus Anthin <e8rasmus@etek.chalmers.se>
Newsgroups: comp.compilers
Date: 22 Jun 2000 01:43:11 -0400
Organization: Chalmers University of Technology
Keywords: parse, question



I have a problem. It seems that I have to have more lookahead tokens than
necessary (and that is really a pain). My CFG in EBNF looks as follows:


//-----------------------------


<program>::= <initiations><main><functions> "|||"
<initiations>::= {<libraries>|<declarations>}
<functions>::= {<function>}
<libraries>::= "use" "(" <library> {"," <library>} ")"
<library>::= <ID>


<declarations>::= <define-type>|<declare-var>
<define-type>::= <type-ID> "=" <type-sorts>
<type-sorts>::= <typeset>|<define>|<define-type>|<type-expr>
<define>::= "{" (<such-as>|<enumerate>) "}" [<array>]
<such-as>::= <ID-list> ":" {<expressions>|<declare-list>}+
<declare-list>::= <declare> {"," <declare>}
<declare>::= <ID-list> "{" <type-sorts> | <type-sorts> "}" <ID-list>
<ID-list>::= <ID> {"," <ID>}
<typeset>::= <type-ID> [<array>]
<enumerate>::= <expressions>
<declare-var>::= <init-list> "{" <type-sorts>
                              | <type-sorts> "}" <init-list>
<init-list>::= <init> {"," <init>}
<init>::= <ID>|<assign>
<array>::= "^" "[" <element> {"x" <element>} "]" | "^" <element>
<element>::= ["+"](DIGITS|"inf")


<type-expr>::= <type-rel>[<u-type-rel-op>] {<type-rel-op><type-rel>}
<type-rel>::= <type-primary> {<type-op><type-primary>}
<type-primary>::= "(" <type-expr> ")" | <type-ID> | <assign2> | <literal>
                              | <expr-array> | <neutral>
<type-op>::= "union"|"inter"|"delta"
<type-rel-op>::= "(_"|"_)"|"(="|"=)"
<u-type-rel-op>::= "^c"
<neutral>::= "|0"|"|U"


<assign>::= <ID> "=" <asg-part>
<assign2>::= <ID-use><assign-op><asg-part>
                              | <ID-use><assign-op2>[<asg-part>]
                              | [<asg-part>]<assign-op2><ID-use>
<assign-op>::= "="|"+="|"-="|"*="|"/="
<assign-op2>::= "++"|"--"|"**"|"//"
<asg-part>::= <expression>|<expr-array>|"@"


<ID>::= LETTER {LETTER|DIGIT|"_"}
<ID-use>::= <ID>["[" <index-list> "]"] {"." <ID> ["[" <index-list> "]"]}
<type-ID>::= <ID><extra>
<extra>::= {"+"|"-"}
<index-list>::= <index> {"," <index>}
<index>::= <element>|<slice>
<slice>::= <element> ".." <element> | ".." <element> | <element> ".."


<expressions>::= <expression> {"," <expression>}
<expr-array>::= "(" <sub-array> {"," <sub-array>} ")"
<sub-array>::= <expr-array>|<expression>|"@"|"<>" "=" <expression>


<expression>::= [<u-log-op>] <condition> {<log-op><condition>}
<condition>::= <relation> {<rel-op><relation>}
<relation>::= [<add-op>] <term>[<u-op>] {<add-op><term>[<u-op>]}
<term>::= <factor> {<mul-op><factor>}
<factor>::= <primary> {<pow-op><primary>}
<primary>::= "(" <expression> ")" |<ID-use>|<assign2>|<literal>|<expr-array>|<func-call>
<add-op>::= "+"|"-"
<mul-op>::= "*"|"/"
<pow-op>::= "^"
<rel-op>::= "!="|"=="|"<"|">"|"<="|">="|"~"|"!~"
<u-op>::= "!"
<u-log-op>::= "not"
<log-op>::= "or"|"and"|"xor"|"nor"|"nand"|"xnor"


<literal>::= <string-lit>|<numb-lit>|<imag-lit>| "inf"
<string-lit>::= "'" {<chars>|" "|"=A7"|"!"|"""|"@"|"#"|"=A3"|"$"|"%"|"&"|"/"|"{"|"("|"["|"]"|")"|"}"|"="|"+"|"-"|"^"|"=A8"|"~"|"*"|"\"|"?"|"."|":"|","|";"|"<"|">"|"|"} "'"
<numb-lit>::= [<add-op>] {<digit>} "." <digits> [("e"|"E") [<add-op>] <digits> ]
=09 | [<add-op>] <digits> [("e"|"E") [<add-op>] <digits> ]
<imag-lit>::= [<numb-lit>] ("i"|"j")


<main>::= [<type-sorts> "}"] "main" "(" [<params>] ")" ":" <initiations><statements> "."
<function>::= [<type-sorts> "}"] <ID> "(" [<params>] ")" ":" <initiations><statements> "."
<params>::= <param> {"," <param>}
<param>::= <declare-var>


<statements>::= {<statement>}|<block>
<block>::= ":" <statements> "."
<statement>::= <assign2>|<control>|<func-call>
<control>::= <for-s>|<while-s>|<until-s>|<if-s>|<case-s>


<for-s>::= <ID> "{" <range> ":" <statements> "."
<range>::= <closed>|<type-sorts>
<closed>::= "[" <element> "," <element> "]"


<while-s>::= <expression> ":" <statements> "."


<until-s>::= ":" <statements> "." <expression>


<if-s>::= <simple-if>|<if>
<simple-if>::= <expression> "=>" <statements>
<if>::= <expression> ":" "=>" <statements> ["!=>" <statements>] "."


<case-s>::= <expression><rel-op> ":" {<expression> "=>" <statements>} ["<>" <statements>] "."


<func-call>::= <ID> "(" <expressions> ")"


//----------------------------------


I know that this seems loco to do in Recursive Descent. But I wan't to
test to make trees with that method. Do anyone have any suggestions
on how to change the CFG to fit into an RDP.


Thankful for any help,
\ B. Rasmus Anthin \ _ ______ |
    / e8rasmus@etek.chalmers.se / `/-==____/__|/__=-|
  / www.etek.chalmers.se/~e8rasmus / * \| |


Post a followup to this message

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