• Post Reply Bookmark Topic Watch Topic
  • New Topic

Implementation of SLR parser  RSS feed

 
harish thiru
Ranch Hand
Posts: 32
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have to implement the construction of slr parsing table and then parse the String given using the table

i have the dragon book where algorithms are given but i have no previous experience of doing any implementation in compiler design

Please get me started I have worked how to parse string given table but i am not able to implement construction of parsing table

any book or source code that can help me please reply

Thanks a lot
 
Sagar Rohankar
Ranch Hand
Posts: 2907
1
Java Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
harish thiru wrote:but i am not able to implement construction of parsing table

Why? Where you get stuck ? Which part you find difficult to implement ?
 
Campbell Ritchie
Marshal
Posts: 56598
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Which edition of the dragon book? Which page?
If the algorithm is given, it is usually easy to convert that to code. What are you using?
 
harish thiru
Ranch Hand
Posts: 32
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
thanks for responding

I have the second edition the four author book from page 241 to 255. I have even the first edition three author book from page 218 to 228

how do implement the goto and closure functions my main problem is the position of parser that is the .
 
Sagar Rohankar
Ranch Hand
Posts: 2907
1
Java Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
harish thiru wrote:
I have the second edition the four author book from page 241 to 255. I have even the first edition three author book from page 218 to 228

Still question is unanswered, which book?
harish thiru wrote:
how do implement the goto and closure functions my main problem is the position of parser that is the .

goto - Java has reserved goto keyword, This links solves your goto problem
closure functions - Java supports OOP, and closure functions, as per my knowledge, access the instance variables which are private.
 
Ernest Friedman-Hill
author and iconoclast
Sheriff
Posts: 24217
38
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Sagar Rohankar wrote:
Still question is unanswered, which book?


He said in his first message: the Dragon Book.
 
harish thiru
Ranch Hand
Posts: 32
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
the goto and closure functions of slr parsing table should i post the algorithm from the book
 
Moojid Hamid
Ranch Hand
Posts: 120
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Sagar Rohankar wrote:goto - Java has reserved goto keyword, This links solves your goto problem
closure functions - Java supports OOP, and closure functions, as per my knowledge, access the instance variables which are private.


Harish is implementing a parser for a simple language (likely school project) hence the SLR parser. The "goto" and "closures" have nothing to do with Java’s goto or the fact that there are no closures in java. These are the constructs that are part of the language being parsed.

This question should be moved to Engineering forum, itis not really a Java question .
 
harish thiru
Ranch Hand
Posts: 32
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
thanks Moojid exactly
 
Sagar Rohankar
Ranch Hand
Posts: 2907
1
Java Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Moojid Hamid wrote: These are the constructs that are part of the language being parsed.

Oops thanks.
 
Campbell Ritchie
Marshal
Posts: 56598
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This is far too complicated a subject to discuss thoroughly here. If I remember correctly (I might be mistaken) a closure is a way of expressing that a production might be made up of repeated elements from the grammar. The goto is a mechanism for traversing the transition table. The transition table shows what states you have reached, and what other tokens may be expected from the input string. Depending on what follows, you can go to the next position by
  • Shifting, which I think means reading the next token onto your stack,
  • Reducing, which I think means going one stage down the list of productions,
  • Accepting, which means the parsing has been completed, or
  • Reporting an error.
  • Except for the very simplest grammars, a transition table can become very large very quickly, so they are very difficult to write, particularly by hand. You will have seen, the pages in the Dragon book you quoted suggest using yacc; there are more recent tools eg JFlex which is a lexer, and CUP. Only CUP is not SLR, it is LALR.
    If you want a top-down parser, most people would look for ANTLR or JavaCC nowadays. There is a fuller list of parsers here.

    I shall leave Fred Martijn and Rob to decide whether to move this thread or not.
     
    harish thiru
    Ranch Hand
    Posts: 32
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Thanks Ritchie for letting me know there is YACC.
    My assignment has been revised If i could construct Simple LR parsing table for the grammar productions given in a file and parse the input string using the table.
    we could use YACC though I am not clear as YACC uses LALR Parsing table.


    I have tried something like this


    I know I am nowhere in constructing Simple LR parsing table for this Grammar productions
    I have never used YACC and i will try to refer books on it. Any suggestions about using YACC
    Thanks a lot for anybody who could help me




     
    harish thiru
    Ranch Hand
    Posts: 32
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Could someone make me clear about this YACC and how to use it in general.
    how i could use it in my assignment.
     
    Campbell Ritchie
    Marshal
    Posts: 56598
    172
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    There are whole books about these parsing tools; I have a copy of this at home.
     
    Moojid Hamid
    Ranch Hand
    Posts: 120
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    If I remember right, YACC produces a LALR parser, not Simple LR (SLR) that you are looking for, someone please correct me if I am wrong.

    Second issue with YACC/Bison is that they output C code, Harish you stated this thread in Java forum making me believe you are looking for a solution in Java, YACC may not be the solution you are looking for. As Campbell mentioned there are other solutions that output Java code.
     
    Campbell Ritchie
    Marshal
    Posts: 56598
    172
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I think you are correct that yacc (not "YACC") is LALR.
     
    harish thiru
    Ranch Hand
    Posts: 32
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    thanks Ritchie I am getting the lex and yacc oreilly book.

    Second issue with YACC/Bison is that they output C code,

    But i downloaded parser generator which has yacc and lex can output C, C++, java code and it can produce the slr parser -- correct me if i am wrong, The link for download is http://www.bumblebeesoftware.com/downloads.htm
    In my assignment it does not matter which programming language,i thought i would choose java since it would be much easy, it has StringTokenizer class,etc. But i have to use yacc
     
    Ulf Dittmer
    Rancher
    Posts: 42972
    73
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    But i read now parser generators can output C, C++, java code -- correct me if i am wrong

    Parser generators are a technology - they can be made to output whatever you want. But any particular package may happen to output C code only. It looks like Bison can be made to output Java, though; see http://www-serl.cs.colorado.edu/~serl/misc/jb.html and http://www.gnu.org/software/bison/manual/html_node/Java-Bison-Interface.html
     
    harish thiru
    Ranch Hand
    Posts: 32
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I downloaded from the link. The read me file says
    The Parser Generator versions of YACC and Lex
    • Generate C, C++ and Java parsers and lexical analysers.
    • AYACC can generate LALR(1), CLR(1) and SLR(1) parsers

    These are two things it says i didn't understand much.i'l read more in books and try then maybe i'l understand
     
    Campbell Ritchie
    Marshal
    Posts: 56598
    172
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    harish thiru wrote: . . . These are two things it says i didn't understand . . .
    Writing compilers and parsers is a science in itself. There is a lot to understand.

    Please tell us what you didn't understand.
     
    harish thiru
    Ranch Hand
    Posts: 32
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I have tried with the above parser generator the productions
    E->E+T
    E->T
    T->T*F
    T->F
    F->(E)
    F->d // d is a digit

    I have written the following lex code


    It is there in the dragon book .I put the *.y extension and then compiled and in the Parser wizard of the IDE I choose the target language as java
    then i get the following code has output It is full of errors and C syntax correct me if i am wrong I have no idea what is happening I know I have to then compile. I choose C as the target language also then also i get it is not compiling in Borland C++. It says Cannot open include file: 'yycpars.h'


    Anyone can help me what is happening thanks a lot
     
    Campbell Ritchie
    Marshal
    Posts: 56598
    172
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Apart from the fact that term'*'factor {$$ = $1 + $3;) is obviously mistaken, no. Transition table code is completely incomprehensible to the human eye.
    You will need to work out where the yycpars.h file is. Are you sure it shouldn't be #include "yycpars.h"??
     
    harish thiru
    Ranch Hand
    Posts: 32
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    sorry yeah it is #include "yycpars.h" . It is there in the cpp include folder in parser generator I do not know how to compile making visual C++ include those header files in include folder i tried copying it does not work.It still says not found.I found out out to use java then I haave to change the syntax of my lex code.
     
    Moojid Hamid
    Ranch Hand
    Posts: 120
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    harish thiru wrote:I found out out to use java then I haave to change the syntax of my lex code.


    could not quite understand what you were saying there, if you have not found out yet, I would suggest you start here
     
    harish thiru
    Ranch Hand
    Posts: 32
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Thanks Moojid very nice link very clearly explained.
    Sorry in urgency i did lot of typing mistakes

    Now i used my parser generator to generate java code for the same link you gave but in the java file using netbeans even after finding the package yl and copy pasting it I am getting lot of errors i posted some part of code



     
    Ulf Dittmer
    Rancher
    Posts: 42972
    73
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    It would be useful if you posted the error messages in addition to the code that causes them.
     
    harish thiru
    Ranch Hand
    Posts: 32
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    The Netbeans says cannot find class YYSTYPE even though i imported the yl package.Many cannot find symbol errors.

    cannot find symbol
    symbol : class yyftables
     
    Campbell Ritchie
    Marshal
    Posts: 56598
    172
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    NetBeans? Are you using Java or C for your code? I thought your YYSTYPE types were specific to using lex and yacc in C.
     
    harish thiru
    Ranch Hand
    Posts: 32
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I could use anything now I used java that is in the ParserWizard i put the option output code Java

    I used this code


    Could you please tell what is the mistake I am doing The code is from the link Moojid posted.
     
    • Post Reply Bookmark Topic Watch Topic
    • New Topic
    Boost this thread!