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 
Welcome to LinuxQuestions.org, a friendly and active Linux Community.
You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!
Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.
Are you new to LinuxQuestions.org? Visit the following links:
Site Howto 
Site FAQ 
Sitemap 
Register Now
If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.
Having a problem logging in? Please visit this page to clear all LQrelated cookies.

Introduction to Linux  A Hands on Guide
This guide was created as an overview of the Linux Operating System, geared toward new users as an exploration tour and getting started guide, with exercises at the end of each chapter.
For more advanced trainees it can be a desktop reference, and a collection of the base knowledge needed to proceed with system and network administration. This book contains many real life examples derived from the author's experience as a Linux system and network administrator, trainer and consultant. They hope these examples will help you to get a better understanding of the Linux system and that you feel encouraged to try out things on your own.
Click Here to receive this Complete Guide absolutely free. 



03312010, 03:35 PM

#1

LQ 5k Club
Registered: Sep 2009
Posts: 6,443

Could someone help explain this code?
http://llvm.org/docs/tutorial/LangImpl2.html
I tried implementing that before and went pretty far, but I got stuck at the op precedence part.
Anyway, is that a recursive descent parser?
And can someone help explain how the operator precedence works?



03312010, 03:58 PM

#2

Guru
Registered: Dec 2007
Distribution: Centos
Posts: 5,044

Quote:
Originally Posted by MTK358
Anyway, is that a recursive descent parser?

If you compared it against any rigorous definition of "recursive descent parser", it doesn't match.
But the basic concepts are the same. So it is something similar to a "recursive descent parser".
Quote:
can someone help explain how the operator precedence works?

What about it?
How operator precedence "works" in the language made up for that tutorial?
Or how the ParseBinOpRHS function in that tutorial implements the rules of operator precedence?
That function is called whenever the parser has an expression that might be the left hand operand of some larger expression.
Assuming there is a binary operator as the next token, making it possible for the current expression to be its left hand operand:
The function first must decide whether that expression is instead the right hand operand of some larger expression being processed by the (recursive) caller. It does so by comparing the precedence passed in by that caller to the next token's precedence.
If the expression is the left operand of the next token, the function must then find the right operand of that token. To do so, it advances past the token and parses a primary expression. That primary expression might be the desired right operand or it might left operand of a subexpression and that whole subexpression would be the desired right operand. So the function uses itself recursively to construct its right operand.
Last edited by johnsfine; 03312010 at 04:07 PM.



03312010, 04:01 PM

#3

LQ 5k Club
Registered: Sep 2009
Posts: 6,443
Original Poster

Quote:
Originally Posted by johnsfine
How operator precedence "works" in the language made up for that tutorial?
Or how the ParseBinOpRHS function in that tutorial implements the rules of operator precedence?

I am talking about how the ParseBinOpRHS function figures out the precedence.



03312010, 04:22 PM

#4

Guru
Registered: Dec 2007
Distribution: Centos
Posts: 5,044

Quote:
Originally Posted by MTK358
I am talking about how the ParseBinOpRHS function figures out the precedence.

I was editing that part of my reply when you posted, so reread above if you haven't yet.



03312010, 08:04 PM

#5

LQ 5k Club
Registered: Sep 2009
Posts: 6,443
Original Poster

I'm still having difficulty understanding it, but it slightly makes sense.
I was wondering if it could be easier just to do it this way?
And no matter what method, how do you handle left/right accociativity?
Code:
expr ::= expr2 "+" expr2
 expr2 "" expr2
 expr2
expr2 ::= expr3 "*" expr3
 expr3 "/" expr3
 expr3
expr3 ::= NUMBER
 VARIABLE
 "" expr3
 ( expr )



04012010, 07:09 AM

#7

LQ 5k Club
Registered: Sep 2009
Posts: 6,443
Original Poster

Quote:
Originally Posted by Sergei Steshenko
Oh, now C++ .

Because I had already partially wrote it before.
If you insist that Perl will really be better, then maybe... , because I really am intrigued by the idea of storing AST nodes as hashes.
Quote:
Originally Posted by Sergei Steshenko

Still I don't think I understand it really well.
Last edited by MTK358; 04012010 at 07:12 AM.



04012010, 07:18 AM

#8

Senior Member
Registered: May 2005
Posts: 4,481

Quote:
Originally Posted by MTK358
Because I had already partially wrote it before.
If you insist that Perl will really be better, then maybe...
Still I don't think I understand it really well.

I am not saying Perl is really better, but in Perl everything is "elastic" by default, and there is no type strictness which in this case is good  again, you do not have to plan ahead, say, fields in a data structure describing a tree node, you just add hash keys.
Regarding "I don't think I understand it really well"  here is a very simple question for you: how (step by step) as a human do you calculate the following expression:
Code:
1 + 2 + 3 + 4 * 5 ^ 2
?
'^' is power operation (i.e. 2 ^ 3 is 8) which has higher precedence than other arithmetic operations. I emphasize the point  step by step.



04012010, 07:25 AM

#9

LQ 5k Club
Registered: Sep 2009
Posts: 6,443
Original Poster

Quote:
Originally Posted by Sergei Steshenko
I am not saying Perl is really better, but in Perl everything is "elastic" by default, and there is no type strictness which in this case is good  again, you do not have to plan ahead, say, fields in a data structure describing a tree node, you just add hash keys.

I guess it might be worth a try.
Quote:
Originally Posted by Sergei Steshenko
Regarding "I don't think I understand it really well"  here is a very simple question for you: how (step by step) as a human do you calculate the following expression:
Code:
1 + 2 + 3 + 4 * 5 ^ 2
?
'^' is power operation (i.e. 2 ^ 3 is 8) which has higher precedence than other arithmetic operations. I emphasize the point  step by step.

I still don't really understand the kind of answer you expect from this kind of question, but here goes...
I look at all the operators and find the '^', that has the highest precedence. I solve it and replace "5 ^ 2" with "25".
Then I see the '*', which has higher precedence than the rest. I replace "4 * 25" with 100.
Then, because the rest is addition and it doesn't matter which way you add them, I just add all the remaining numbers up.



04012010, 07:41 AM

#10

Senior Member
Registered: May 2005
Posts: 4,481

Quote:
Originally Posted by MTK358
I guess it might be worth a try.
I still don't really understand the kind of answer you expect from this kind of question, but here goes...
I look at all the operators and find the '^', that has the highest precedence. I solve it and replace "5 ^ 2" with "25".
Then I see the '*', which has higher precedence than the rest. I replace "4 * 25" with 100.
Then, because the rest is addition and it doesn't matter which way you add them, I just add all the remaining numbers up.

The item in bold is the evidence I've been expecting "forever". And this evidence really proves my suspicions about things you do not understand. And I'll try to help you to understand them right.
So now let's change the task by "scaling". Again, let's take the same expression:
Code:
1 + 2 + 3 + 4 * 5 ^ 2
and let's imagine that its "head" of "pluses", i.e.
is very very long, like thousand(s) of members. Other than that the expression is the same.
Let's also assume that each operand is written, say, as 30cm/1foot high/wide digit (approximately), and it's written on a wall. Similarly, operation signs ('+', '*', '^' in this case) are also written kinda in 30cm x 30cm cells, and your eyes distance from the wall is also about 30cm/1foot, i.e. at a time you can see just one operand or one operation sign. You also have a notebook (I mean paper one), a pencil and an eraser, so you can take notes and read them as needed.
You are put at the left side of the expression and because of the above conditions, as I said, you can only see what is now the leftmost '1'.
How would you calculate the expression under such circumstances ? You are not allowed (and do no need) to run to the other end in order to see the whole expression. Remember, the expression occupies at least 1000 feet (300m) on the wall, so, again, there is no chance you see its tail.
I reiterate, you can see either one operand or one operation sign at a time, and you can take notes.
And let's assume you are constructively lazy, i.e. you want to perform minimum amount of moves along the wall.
Again, step by step actions you'll perform as a human.



04012010, 09:37 AM

#11

LQ 5k Club
Registered: Sep 2009
Posts: 6,443
Original Poster

I am not sure, I guess I might do it like this:
I would go past the first number, the plus, and the next number.
Then I check the next operator and it's another plus. Since it's leftassociative, I see if it's precedence is > than the previous plus.
It's not, so I calculate the first +expression and move on...
Then I get to the multiplication. It's leftassociative, so I check if it's precedence > than of the plus. It is, so I skip to the multiplication.
But I first see what the next operator is. It's a ^, and it's rightaccociative, so I see if it's precedence ≥ the * operator.
It is, so I see the next one. But there is no next one, so I do the ^, then fall back to the *, and to the +.



04012010, 09:55 AM

#12

Senior Member
Registered: May 2005
Posts: 4,481

Quote:
Originally Posted by MTK358
I am not sure, I guess I might do it like this:
I would go past the first number, the plus, and the next number.
Then I check the next operator and it's another plus. Since it's leftassociative, I see if it's precedence is > than the previous plus.
It's not, so I calculate the first +expression and move on...
Then I get to the multiplication. It's leftassociative, so I check if it's precedence > than of the plus. It is, so I skip to the multiplication.
But I first see what the next operator is. It's a ^, and it's rightaccociative, so I see if it's precedence ≥ the * operator.
It is, so I see the next one. But there is no next one, so I do the ^, then fall back to the *, and to the +.

You are on the right track.
Now regarding the item in bold  I have a "bad news" for you  no matter how you formulate, but in fact it really means:
"if current operator (after which there is an operand) is followed by by an operator with higher precedence, then I do this and that". Likewise, similar statements with followed by can be formulated with equal and lower precedence.
Back to our sheep  assume now that your notebook has sheets with pretty big cells in it. The cell is big in a sense you can write some name in it  like 'operand', 'operation', etc., but the cell is still small in a sense it can contain just one item. So, for example, in a cell named 'operation' you can have '+' or '*' or '^', but no more than that. And in a cell named 'operand' you can have '1', '2', etc  just any one of the operands present in the expression.
In the beginning you may have as many cells as you like, but ultimately try to minimize number of needed cells.
So, now fully document your steps for the
Code:
1 + 2 + 3 + 4 * 5 ^ 2
expression (not that many steps) including all the decision making (your 'if ... else' statements above). Fully document means introduce some cell names and describe what you write into the cells, as well as what checks you make. Remember, you also have an eraser, i.e. you can, if appropriate, change value in a cell  not only write value into it
Having all this before your and my eyes will really help to draw further algorithmic conclusions and get closer to real code.
Of course, your final calculated result should be correct.



04012010, 10:04 AM

#13

Guru
Registered: Dec 2007
Distribution: Centos
Posts: 5,044

Quote:
Originally Posted by MTK358
I was wondering if it could be easier just to do it this way?

I assume you mean the grammar rules you showed.
First, those grammar rules are wrong. They couldn't even handle A+B+C. Probably you meant:
Code:
expr ::= expr "+" expr2
 expr "" expr2
 expr2
expr2 ::= expr2 "*" expr3
 expr2 "/" expr3
 expr3
expr3 ::= NUMBER
 VARIABLE
 "" expr3
 ( expr )
Second, grammar rules do not imply a method to implement them.
Notice these corrected rules define an infinite recursion if you take a simplistic recursive approach to parsing. Try to parse an expr and the first thing to check is whether it starts with an expr. That is infinite recursion before you even look at anything.
Quote:
And no matter what method, how do you handle left/right accociativity?

The corrected rules show the basis for left right associativity. Consider A+B+C:
A+B could be an expr or B+C could be an expr.
If A+B is an expr then that expr + C is another expr. But if B+C is an expr, then A plus that expr is not represented by this grammar.
Last edited by johnsfine; 04012010 at 10:10 AM.



04012010, 10:16 AM

#14

LQ 5k Club
Registered: Sep 2009
Posts: 6,443
Original Poster

I see the "1".
Then the '+'.
Then the '2'.
I make this tree: (+, 1, 2)
I check the next operator. It's left associative, and its precedence is not greater than that of the previous operator.
I then get the next number and continue the tree like this: (+, (+, 1, 2), 3)
Now the the next +. The next operator after it is leftassociative and has a higher precedence. So I recursively start from there.
The next operator (^) is rightassociative and is greater than or equal to the previous one. I again go further recursively.
There is no next operator. I return back to the multiplication with this tree: (^, 5, 2)
The multiplication function finds there is no next operator now. It returns this tree: (*, 4, (^, 5, 2))
The first level now finds there are no more operators, and returns this: (+, (+, (+, 1, 2), 3), (*, 4, (^, 5, 2)))
EDIT: I did not see the reply by johnsfine
Last edited by MTK358; 04012010 at 10:17 AM.



04012010, 10:23 AM

#15

Senior Member
Registered: May 2005
Posts: 4,481

Quote:
Originally Posted by MTK358
I see the "1".
Then the '+'.
Then the '2'.
I make this tree: (+, 1, 2)
I check the next operator. It's left associative, and its precedence is not greater than that of the previous operator.
I then get the next number and continue the tree like this: (+, (+, 1, 2), 3)
Now the the next +. The next operator after it is leftassociative and has a higher precedence. So I recursively start from there.
The next operator (^) is rightassociative and is greater than or equal to the previous one. I again go further recursively.
There is no next operator. I return back to the multiplication with this tree: (^, 5, 2)
The multiplication function finds there is no next operator now. It returns this tree: (*, 4, (^, 5, 2))
The first level now finds there are no more operators, and returns this: (+, (+, (+, 1, 2), 3), (*, 4, (^, 5, 2)))
EDIT: I did not see the reply by johnsfine

Let's first implement treeless calculation on the fly. The point is to better show/feel how much of already processed part of expression you really need for calculations/decision making.
Secondly, the tree is a "book" one, but not necessarily the most convenient one. For many practical tasks a tree like this:
Code:
(+, 1, 2, 3, (*, 4, (^, 5, 2)))
is much more convenient.



Thread Tools 
Search this Thread 


Posting Rules

You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is Off



All times are GMT 5. The time now is 11:55 PM.

LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.

Latest Threads
LQ News

