LinuxQuestions.org
Visit Jeremy's Blog.
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-17-2010, 01:06 AM   #31
larryherman
LQ Newbie
 
Registered: Sep 2003
Distribution: RHEL, SUSE, SLED
Posts: 12

Rep: Reputation: 2

Quote:
Originally Posted by MTK358 View Post
The problem is that I hardly understand anything in Calculator -> Description!

I'm not sure what your background is, but I first used lex and yacc after having taken a compilers course, so I was familiar with the background concepts, which may be difficult if you haven't seen them before. Depending upon your experience, you might start with a good compilers text and read about scanning and bottom-up parsing before really trying to use lex and yacc, which, after all, are tools to do those things.

My compilers text is rather old, so maybe someone else can recommend a more recent one if you're inclined to do some reading first (although actually I doubt the concepts have changed at all).
 
Click here to see the post LQ members have rated as the most helpful post in this thread.
Old 03-17-2010, 04:57 PM   #32
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 larryherman View Post
I'm not sure what your background is
I basically know all I know about computers and programming from the internet!

Anyway, I was considering using a tree node structure that contains a name, value, and child nodes to represent the syntax tree.

A function that would print the tree recursively might be something like this, where each node structure stores it's name, value, and a NULL-terminated array of child nodes:

Code:
int level = 0;

void print_tree(struct node* root) {
	int i;
	for(i=0; i<level; i++) {
		printf("    ");
	}
	//TODO: print node's name and value
	level++;
	for(i=0; tree->children[i] != NULL; i++) {
		print_tree(tree->children[i]);
	}
	level--;
}

Last edited by MTK358; 03-17-2010 at 05:00 PM.
 
Old 03-17-2010, 05:02 PM   #33
Sergei Steshenko
Senior Member
 
Registered: May 2005
Posts: 4,481

Rep: Reputation: 453Reputation: 453Reputation: 453Reputation: 453Reputation: 453
Quote:
Originally Posted by MTK358 View Post
I basically know all I know about computers and programming from the internet!

Anyway, I was considering using a tree node structure that contains a name, value, and child nodes to represent the syntax tree.

A function that would print the tree recursively might be something like this, where each node structure stores it's name, value, and a NULL-terminated array of child nodes:

Code:
int level = 0;

void print_tree(struct node* root) {
	int i;
	for(i=0; i<level; i++) {
		putchar(' ');
	}
	//TODO: print node's name and value
	level++;
	for(i=0; tree->children[i] != NULL; i++) {
		print_tree(tree->children[i]);
	}
	level--;
}
If it is not a homework/paid job strictly requiring lex/yacc better do it in Perl (or similar language). In Perl AST (Abstract Syntax Tree) is just a hierarchical data structure, and to dump it you cab easily use Data:umper module.

You would also be able to dump AST into a file and consume it in another script. I've been successfully using this approach for years in/for serious EDA related stuff.

Last edited by Sergei Steshenko; 03-18-2010 at 01:40 PM.
 
0 members found this post helpful.
Old 03-18-2010, 12:58 PM   #34
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 am slowly getting to understand the Calculator example, and I finally got it to compile!

Code:
$ cat euclidian-algorithm.txt 
a = 12;
b = 8;
while(a != b) {
        if(a > b) {
                a = a - b;
        } else {
                b = b - a;
        }
}
$ ./calc3g < euclidian-algorithm.txt 


Graph 0:

     [=]
      |
   |-----|
   |     |
 id(A) c(12)


Graph 1:

    [=]
     |
   |----|
   |    |
 id(B) c(8)


Graph 2:

                            while
                              |
      |-----------------------------|
      |                             |
    [!=]                           if
      |                             |
   |-----|        |--------------|-----------------|
   |     |        |              |                 |
 id(A) id(B)     [>]            [=]               [=]
                  |              |                 |
               |-----|     |--------|        |--------|
               |     |     |        |        |        |
             id(A) id(B) id(A)     [-]     id(B)     [-]
                                    |                 |
                                 |-----|           |-----|
                                 |     |           |     |
                               id(A) id(B)       id(B) id(A)
The grapher really explains a lot about how this all works.
 
Old 03-18-2010, 05:03 PM   #35
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'm slowly making some progress I already wrote most of the Lex and YACC files for an interpreter that puts together a syntax tree structure and parses it.

I'm pretty sure I omitted a lot of important stuff, could you give me any suggestions?
Attached Files
File Type: txt lang.l.txt (262 Bytes, 6 views)
File Type: txt lang.y.txt (2.1 KB, 7 views)
 
Old 03-18-2010, 05:49 PM   #36
theNbomr
LQ 5k Club
 
Registered: Aug 2005
Distribution: OpenSuse, Fedora, Redhat, Debian
Posts: 5,395
Blog Entries: 2

Rep: Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903
Looks pretty good, considering that a short while ago you said:
Quote:
The problem is that I hardly understand anything in Calculator -> Description!
Right off the bat I see the definition for an integer is a little weak. Your regex matches any single digit. A more complete regex might look more like
Code:
[+-]?[0-9]+
Hard to see errors just by inspection. I assume you are using the more complex form of building up the tree in anticipation of adding conditionals/branching to your grammar.
Well done.
--- rod.
 
Old 03-18-2010, 08:24 PM   #37
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
Right off the bat I see the definition for an integer is a little weak. Your regex matches any single digit. A more complete regex might look more like
Code:
[+-]?[0-9]+
But doesn't Lex match the token whose regex matches the most characters? If so, then this:

4-3

will be interpreted as:

4
-3

instead of

4
-
3

, which is invalid. I thought that it would work right if you would implement negation as part of the grammar. That would also let you negate variables, and expressions in parentheses, not just integer literals.

Quote:
Originally Posted by theNbomr View Post
Hard to see errors just by inspection. I assume you are using the more complex form of building up the tree in anticipation of adding conditionals/branching to your grammar.
Well done.
Yes, the reason I am doing it this way is that I want to add conditionals and looping.

Last edited by MTK358; 03-18-2010 at 08:26 PM.
 
Old 03-18-2010, 08:44 PM   #38
MTK358
LQ 5k Club
 
Registered: Sep 2009
Posts: 6,443
Blog Entries: 3

Original Poster
Rep: Reputation: 714Reputation: 714Reputation: 714Reputation: 714Reputation: 714Reputation: 714Reputation: 714
OK, I tried compiling my code and it has all these errors, I am totally puzzled because I hardly understand the code I wrote in the first place

At least lex and yacc passed without errors first time!

Code:
$ gcc *.c -o lang
lang.l:2:19: error: y.tab.h: No such file or directory
lang.l: In function ‘yylex’:
lang.l:8: error: ‘INTEGER’ undeclared (first use in this function)
lang.l:8: error: (Each undeclared identifier is reported only once
lang.l:8: error: for each function it appears in.)
lang.l:9: error: ‘ASSIGN’ undeclared (first use in this function)
lang.l:10: error: ‘ADD’ undeclared (first use in this function)
lang.l:11: error: ‘SUBTRACT’ undeclared (first use in this function)
lang.l:12: error: ‘MULTIPLY’ undeclared (first use in this function)
lang.l:13: error: ‘DIVIDE’ undeclared (first use in this function)
lang.l:14: error: ‘OPAREN’ undeclared (first use in this function)
lang.l:15: error: ‘CPAREN’ undeclared (first use in this function)
lang.l:16: error: ‘SEPARATOR’ undeclared (first use in this function)
lang.y:12: error: expected specifier-qualifier-list before ‘Node’
lang.y:24: error: redefinition of typedef ‘NodeLitIntValues’
lang.y:19: note: previous declaration of ‘NodeLitIntValues’ was here
lang.y:31: error: expected specifier-qualifier-list before ‘NodeVarValues’
lang.y:35: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘mkLitIntNode’
lang.y:36: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘mkVarNode’
lang.y:37: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘mkOpNode’
lang.y:38: error: expected ‘)’ before ‘n’
lang.y:39: error: expected ‘)’ before ‘n’
lang.y:76: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘mkLitIntNode’
lang.y:83: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘mkVarNode’
lang.y:90: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘mkOpNode’
lang.y:105: error: expected ‘)’ before ‘*’ token
lang.y:129: error: expected ‘)’ before ‘*’ token
Attached Files
File Type: txt lang.l.txt (263 Bytes, 4 views)
File Type: txt lang.y.txt (2.8 KB, 3 views)
 
Old 03-18-2010, 09:49 PM   #39
theNbomr
LQ 5k Club
 
Registered: Aug 2005
Distribution: OpenSuse, Fedora, Redhat, Debian
Posts: 5,395
Blog Entries: 2

Rep: Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903
Quote:
Originally Posted by MTK358 View Post
, which is invalid. I thought that it would work right if you would implement negation as part of the grammar. That would also let you negate variables, and expressions in parentheses, not just integer literals.
Yes, good point. Associativity and precedence in the grammar are the key to that.
Code:
lang.l:2:19: error: y.tab.h: No such file or directory
They y.tab.h header file declares &/or defines all of the symbols missing from your compilation. It is generated by yacc from the grammar.
---- rod.
 
Old 03-18-2010, 11:29 PM   #40
larryherman
LQ Newbie
 
Registered: Sep 2003
Distribution: RHEL, SUSE, SLED
Posts: 12

Rep: Reputation: 2
Unary minus

Section 5.4 of the Bison manual that I mentioned earlier illustrates how to handle the unary minus:
http://www.gnu.org/software/bison/ma...ual-Precedence. Give it a try.
 
Old 03-19-2010, 09:05 AM   #41
MTK358
LQ 5k Club
 
Registered: Sep 2009
Posts: 6,443
Blog Entries: 3

Original Poster
Rep: Reputation: 714Reputation: 714Reputation: 714Reputation: 714Reputation: 714Reputation: 714Reputation: 714
@theNbomr

For some reason I run yacc, then lex, and it doesn't create a "y.tab.h" file!

@larryherman

I implemented that in my code now.
 
Old 03-19-2010, 01:28 PM   #42
larryherman
LQ Newbie
 
Registered: Sep 2003
Distribution: RHEL, SUSE, SLED
Posts: 12

Rep: Reputation: 2
Quote:
Originally Posted by MTK358 View Post

For some reason I run yacc, then lex, and it doesn't create a "y.tab.h" file!
bison's -d switch cases it to write an output file with definitions of the token types used in the grammar, etc., but by default it's not named y.tab.h (the name yacc uses). Instead it's named name.h, where the parser output file is name.c. If you want it named y.tab.h you can use bison's -y option, but otherwise just substitute the name of the file that bison actually generates where theNbomr had written y.tab.h.

(If you're actually using yacc rather than bison just ignore the above, but if you're using Linux then yacc may just be a one-line shell script exec'ing bison.)

Hope this helps.
 
Old 03-19-2010, 01:52 PM   #43
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:
$ cat /usr/bin/yacc
#! /bin/sh
exec '/usr/bin/bison' -y "$@"
$ ls
lang.l  lang.y
$ yacc lang.y
conflicts: 4 shift/reduce
$ ls
lang.l  lang.y  y.tab.c

Last edited by MTK358; 03-19-2010 at 01:54 PM.
 
Old 03-19-2010, 04:29 PM   #44
larryherman
LQ Newbie
 
Registered: Sep 2003
Distribution: RHEL, SUSE, SLED
Posts: 12

Rep: Reputation: 2
Can't say why the -y option to bison (in that script) doesn't seem to have the advertised effect, but the -d option to bison works for me, generating the file file.tab.h (from file.y).
 
Old 03-19-2010, 04:43 PM   #45
MTK358
LQ 5k Club
 
Registered: Sep 2009
Posts: 6,443
Blog Entries: 3

Original Poster
Rep: Reputation: 714Reputation: 714Reputation: 714Reputation: 714Reputation: 714Reputation: 714Reputation: 714
bison -d worked.

I corrected some other minor errors, but what is this:

Code:
$ gcc *.c -o lang
lang.y:13: error: expected specifier-qualifier-list before ‘Node’
lang.y:25: error: redefinition of typedef ‘NodeLitIntValues’
lang.y:20: note: previous declaration of ‘NodeLitIntValues’ was here
lang.y:32: error: expected specifier-qualifier-list before ‘NodeVarValues’
lang.y:36: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘mkLitIntNode’
lang.y:37: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘mkVarNode’
lang.y:38: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘mkOpNode’
lang.y:39: error: expected ‘)’ before ‘n’
lang.y:40: error: expected ‘)’ before ‘n’
lang.y:79: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘mkLitIntNode’
lang.y:86: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘mkVarNode’
lang.y:93: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘mkOpNode’
lang.y:108: error: expected ‘)’ before ‘*’ token
lang.y:134: error: expected ‘)’ before ‘*’ token
Attached Files
File Type: txt lang.y.txt (2.9 KB, 4 views)
File Type: txt lang.l.txt (259 Bytes, 3 views)
 
  


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 07:30 AM.

Main Menu
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