LinuxQuestions.org
Help answer threads with 0 replies.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices



Reply
 
Search this Thread
Old 03-16-2010, 12:32 PM   #16
MTK358
LQ 5k Club
 
Registered: Sep 2009
Posts: 6,443
Blog Entries: 3

Original Poster
Rep: Reputation: 714Reputation: 714Reputation: 714Reputation: 714Reputation: 714Reputation: 714Reputation: 714

Still trying to figure out how to make an interpreter that can do decisions and loops. I doubt that yacc can conditionally parse input or be made to parse a section over and over many times so I don't really know what to do.

Perhaps use yacc to built up some kind of tree of the entire input, and have another C file to parse through it?
 
Click here to see the post LQ members have rated as the most helpful post in this thread.
Old 03-16-2010, 01:16 PM   #17
theNbomr
LQ 5k Club
 
Registered: Aug 2005
Distribution: OpenSuse, Fedora, Redhat, Debian
Posts: 5,396
Blog Entries: 2

Rep: Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903
The link I posted in article #12 of this thread contains an example YACC grammar for a calculator which can do conditionals; if-else, while, etc. The nice part is that it can be built as an interpreter, compiler, or tree-generator. The tree generator can be particularly revealing.

There is also a YACC grammar for Mole BASIC, which I found instructive.

--- rod.

Last edited by theNbomr; 03-16-2010 at 01:20 PM.
 
Old 03-16-2010, 01:31 PM   #18
MTK358
LQ 5k Club
 
Registered: Sep 2009
Posts: 6,443
Blog Entries: 3

Original Poster
Rep: Reputation: 714Reputation: 714Reputation: 714Reputation: 714Reputation: 714Reputation: 714Reputation: 714
Quote:
Originally Posted by theNbomr View Post
larryherman has given some very good advice. I have used A Compact Guide to Lex and Yacc as a reference and tutorial in the past. The O'Reilly book is a bit of a standard for Lex & Yacc. Since the Yacc syntax is one application that uses the more general Backus Naur Format (BNF), you may find some useful online resources by searching for that.
--- rod.
The problem is that I hardly understand anything in Calculator -> Description!

 
Old 03-16-2010, 02:55 PM   #19
theNbomr
LQ 5k Club
 
Registered: Aug 2005
Distribution: OpenSuse, Fedora, Redhat, Debian
Posts: 5,396
Blog Entries: 2

Rep: Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903
I didn't grasp it right away either. That is why the syntax tree generator was so helpful. I see that whatever font is being used when I view the page today makes the ASCII graphics distort. Perhaps building & running the example will create a better visual representation of the tree.
The concept is that the interpreter/compiler builds up a tree structure of nodes which contain elements that are either operators or operands. When the tree is fully populated (a successful parse), it is 'executed', by doing a traversal of the tree, evaluating operands and performing the accordant operations at each node.

This is abstract stuff. Study is required to understand it.

--- rod.
 
Old 03-16-2010, 03:28 PM   #20
MTK358
LQ 5k Club
 
Registered: Sep 2009
Posts: 6,443
Blog Entries: 3

Original Poster
Rep: Reputation: 714Reputation: 714Reputation: 714Reputation: 714Reputation: 714Reputation: 714Reputation: 714
Code:
[michael:calculator]$ ls
calc3.h  calc.y      grapher.c      lex.yy.c
calc.l   compiler.c  interpreter.c  y.tab.c
[michael:calculator]$ gcc lex.yy.c y.tab.c interpreter.c 
calc.l:4:19: error: y.tab.h: No such file or directory
calc.l: In function ‘yylex’:
calc.l:11: error: ‘yylval’ undeclared (first use in this function)
calc.l:11: error: (Each undeclared identifier is reported only once
calc.l:11: error: for each function it appears in.)
calc.l:12: error: ‘VARIABLE’ undeclared (first use in this function)
calc.l:17: error: ‘INTEGER’ undeclared (first use in this function)
calc.l:29: error: ‘GE’ undeclared (first use in this function)
calc.l:30: error: ‘LE’ undeclared (first use in this function)
calc.l:31: error: ‘EQ’ undeclared (first use in this function)
calc.l:32: error: ‘NE’ undeclared (first use in this function)
calc.l:33: error: ‘WHILE’ undeclared (first use in this function)
calc.l:34: error: ‘IF’ undeclared (first use in this function)
calc.l:35: error: ‘ELSE’ undeclared (first use in this function)
calc.l:36: error: ‘PRINT’ undeclared (first use in this function)
interpreter.c:3:19: error: y.tab.h: No such file or directory
interpreter.c: In function ‘ex’:
interpreter.c:12: error: ‘WHILE’ undeclared (first use in this function)
interpreter.c:12: error: (Each undeclared identifier is reported only once
interpreter.c:12: error: for each function it appears in.)
interpreter.c:13: error: ‘IF’ undeclared (first use in this function)
interpreter.c:18: error: ‘PRINT’ undeclared (first use in this function)
interpreter.c:21: error: ‘UMINUS’ undeclared (first use in this function)
interpreter.c:28: error: ‘GE’ undeclared (first use in this function)
interpreter.c:29: error: ‘LE’ undeclared (first use in this function)
interpreter.c:30: error: ‘NE’ undeclared (first use in this function)
interpreter.c:31: error: ‘EQ’ undeclared (first use in this function)
 
Old 03-16-2010, 03:32 PM   #21
devnull10
Member
 
Registered: Jan 2010
Location: Lancashire
Distribution: Slackware Stable
Posts: 547

Rep: Reputation: 115Reputation: 115
I'm not sure about the other errors, but you have to link to the lex library by passing -ll to gcc.
 
Old 03-16-2010, 03:41 PM   #22
MTK358
LQ 5k Club
 
Registered: Sep 2009
Posts: 6,443
Blog Entries: 3

Original Poster
Rep: Reputation: 714Reputation: 714Reputation: 714Reputation: 714Reputation: 714Reputation: 714Reputation: 714
I don't know. It doesn't work with -ll.
 
Old 03-16-2010, 04:00 PM   #23
Sergei Steshenko
Senior Member
 
Registered: May 2005
Posts: 4,481

Rep: Reputation: 453Reputation: 453Reputation: 453Reputation: 453Reputation: 453
MTK358, why have you decided to use Lex/Yacc in the first place ?
 
0 members found this post helpful.
Old 03-16-2010, 07:47 PM   #24
theNbomr
LQ 5k Club
 
Registered: Aug 2005
Distribution: OpenSuse, Fedora, Redhat, Debian
Posts: 5,396
Blog Entries: 2

Rep: Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903
Sergei Steshenko, you make it sound like there is something wrong with lex & yacc. If so, what are your objections, and what would you advocate for in lieu of lex & yacc?
--- rod.
 
1 members found this post helpful.
Old 03-16-2010, 07:55 PM   #25
Sergei Steshenko
Senior Member
 
Registered: May 2005
Posts: 4,481

Rep: Reputation: 453Reputation: 453Reputation: 453Reputation: 453Reputation: 453
Quote:
Originally Posted by theNbomr View Post
Sergei Steshenko, you make it sound like there is something wrong with lex & yacc. If so, what are your objections, and what would you advocate for in lieu of lex & yacc?
--- rod.
No, I am not saying something is wrong with lex/yacc, but to me using lex/yacc looks like a hard way of doing the job.

For starters, it looks unnatural to me to split the task between the two tools.

I much prefer the approach which describes the language to be dealt with as a set a language constructs which can be as little/simple as one character ans as big/complex as the whole input program, module, etc.

For example, a tool whose approach I like is called Elkhound: http://scottmcpeak.com/elkhound/ .

I think there is at least one interesting back-tracking parser in Perl.

I myself wrote a back-tracking parser in Perl about 10 years ago, but it was without memoization ( http://en.wikipedia.org/wiki/Memoization ).
 
Old 03-16-2010, 08:28 PM   #26
theNbomr
LQ 5k Club
 
Registered: Aug 2005
Distribution: OpenSuse, Fedora, Redhat, Debian
Posts: 5,396
Blog Entries: 2

Rep: Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903
Quote:
Originally Posted by Sergei Steshenko View Post
No, I am not saying something is wrong with lex/yacc, but to me using lex/yacc looks like a hard way of doing the job.

For starters, it looks unnatural to me to split the task between the two tools.
I think it is one of those things that is conceptually difficult to understand & somewhat difficult to learn the details sufficiently well to be productive. However, once those hurdles are overcome, it is a very elegant and concise solution to a fairly complex task (as you must well know).
The split between lexical and grammatical parsing makes perfect sense to me. Some jobs can be accomplished without the aid of a grammar, so why ball it all into one when not necessary? It seems very much in the spirit of Unix; individual tools that do one thing very well.

I will have a look at Elkhound. These kinds of things are a bit of a subject of fascination to me.

--- rod.
 
Old 03-16-2010, 08:37 PM   #27
MTK358
LQ 5k Club
 
Registered: Sep 2009
Posts: 6,443
Blog Entries: 3

Original Poster
Rep: Reputation: 714Reputation: 714Reputation: 714Reputation: 714Reputation: 714Reputation: 714Reputation: 714
I looked at Elkhound and I see that it uses C++, and I would rather use C.

The main stumbling block for me now is not that I have such a poor understanding of what YACC does, but I don't know how to write the additional code that interprets decisions and loops, and how to interface it with Lex and YACC.
 
Old 03-16-2010, 09:15 PM   #28
Sergei Steshenko
Senior Member
 
Registered: May 2005
Posts: 4,481

Rep: Reputation: 453Reputation: 453Reputation: 453Reputation: 453Reputation: 453
Quote:
Originally Posted by theNbomr View Post
...
The split between lexical and grammatical parsing makes perfect sense to me. Some jobs can be accomplished without the aid of a grammar, so why ball it all into one when not necessary? It seems very much in the spirit of Unix; individual tools that do one thing very well.
...
And my point is that I'm lazy, and I'd rather learn a single concept of what I call a language construct rather than two concepts/approaches represented by lex and yacc.

I first learned the concept from Prolog - the lecturer in detail explained how matching was performed.

I am not a fashionable guy, but modern parsers are of the Elkhound flavor. I think I actually came across Elkhound looking for parser generator in OCaml - Elkhound was mentioned on the corresponding OCaml page.

It's a breeze to write a complete product - first the parser itself (grammar, constructs recognition) is debugged, then callbacks are added. It's also a breeze to debug - it's easy to track tracking (tautology intended); in my own Perl parser I did this a lot, language constructs tracking was implemented with indentation, so it was easy to understand the debug output.
 
Old 03-16-2010, 09:20 PM   #29
Sergei Steshenko
Senior Member
 
Registered: May 2005
Posts: 4,481

Rep: Reputation: 453Reputation: 453Reputation: 453Reputation: 453Reputation: 453
The Perl module: http://search.cpan.org/~arthur/Parse...se/Stallion.pm - resembles a lot what I've done, which is natural because we both tried to solve the same problems.

...

A Perl module with calculator as an example: http://search.cpan.org/~dconway/Rege...xp/Grammars.pm .

Another module: http://search.cpan.org/~jkegl/Parse-...Parse/Marpa.pm .
 
Old 03-16-2010, 10:59 PM   #30
sundialsvcs
Guru
 
Registered: Feb 2004
Location: SE Tennessee, USA
Distribution: Gentoo, LFS
Posts: 5,455

Rep: Reputation: 1172Reputation: 1172Reputation: 1172Reputation: 1172Reputation: 1172Reputation: 1172Reputation: 1172Reputation: 1172Reputation: 1172
Here's a good way to think about it ...

Sure, for "a calculator," lexx and yacc are probably overkill. But this is intended to be a simple demonstration.

Lexx and Yacc are tools that are designed to, if you will, "navigate a road map ... any road map." They let you construct the road map (the "grammar"), which describes the lay of the land, and to add specific instructions that should be carried-out whenever a particular point on the map has been reached. (These are how calls are made to your back-end routines.)

These tools are strong enough to be used to build a simple calculator ... or a "C" compiler. They really show their worth when you need to handle "a complicated input" without having to build a complicated computer program in order to do it.

The behavior of the parser is complicated ... but the parser is not. ("It's just clever, that's all...")

You can feed any source-program, however complex, into a parser that's built using these tools and ... as if by magic ... the right calls will be made at the right time. If a syntax-error is discovered, the parser is capable of helping you "find a place where you can try to keep going, now to find more syntax errors if you can."

And, it works for anything. If you can build a grammar for it, Lexx/Yacc can (probably) parse it. R-a-p-i-d-l-y...

It's a very special-purpose tool. But, get to know it anyway. "When you need it, you will know."

Last edited by sundialsvcs; 03-16-2010 at 11:02 PM.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
lex and yacc in RHEL4 birds Linux - Software 1 06-03-2009 03:56 AM
LEX and YACC with C gr33ndata Programming 4 11-18-2007 06:12 PM
Lex and Yacc on Federo 2.0 vivekian Fedora 6 05-20-2006 10:09 AM
Lex and Yacc on Mandrake 9.2.2 Anuradha Linux - Software 0 07-02-2005 04:32 AM
Lex & YACC coolfrog Programming 3 09-25-2004 08:00 AM


All times are GMT -5. The time now is 03:58 PM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration