#### bison/yacc: shift/reduce conflict using %prec for composition

Would someone explain why a simple grammar such as this:

%left FUNCTION

%%

expr: 'A'
| expr expr %prec FUNCTION
;

causes a shift/reduce conflict in bison/yacc? Here is how I understand
my generated parser will work: all input must consist of a series of
the terminal 'A', which will be identified as an expr; when two exprs
are found adjacent, i.e., two 'A's, they will be reduced by the
left-to-right precedence declared by the %prec modifier. I thus see no
reason for a shift/reduce conflict.
[It's because precedences are attached to tokens, and there's no tokens
in that rule. -John]


 0
6/25/2004 5:52:06 AM
comp.compilers 3230 articles. 0 followers.

1 Replies
980 Views

Similar Articles

[PageSpeed] 47
longjonathan@comcast.net (J Long) wrote
> Would someone explain why a simple grammar such as this
>
> %left FUNCTION
>
> %%
>
> expr: 'A'
>     | expr expr %prec FUNCTION
> ;
>
> causes a shift/reduce conflict in bison/yacc?
> [It's because precedences are attached to tokens, and there's no tokens
> in that rule. -John]

The esteemed moderator is almost right -- precedences are indeed on
tokens, but they are also on rules, which get precendences either from
their left-most token or from an explicit %prec declaration as above.

The problem in the above grammar is that 'A' has no precedence.

To understand this problem, you really need to understand in some
deatil how shift-reduce parsing works.  Basically, at each state in
the machine, the parser looks at the next token to decide if it should
shift that token or reduce some rule.  You get shift/reduce or
reduce/reduce conflicts if bison/yacc can't decide which it should be.
Precedence rules allow you to resolve these conflicts by telling it.

When there's a shift/reduce conflict, bison will compare the
precedence of the token to be shifted with the precedence of the rule
to be reduced.  Whichever is higher gets done.  So for the above
grammar, after having parsed two expressions, if it sees an 'A' it
needs to decide whether to reduce the two expressions to one, or shift
the A and parse more expressions.

So you neeed to give 'A' a higher precedence than FUNCTION, or, as it
declared left', the same precedence.

To generalize this to more expressions, you need need to give any
token that might start an expression the same precedence as 'A'.  This
can cause problems if you have some token that might be both the first
token in an expression, and some sort of infix operator, such as '-'.
In this case, you really want to give '-' two different precedences
depending on context.  Unfortuntely there's no way to do that with
bison.  The only real solution then is to use new non-terminal rules
instead of precendences to deal with the ambiguities.

Chris Dodd
cdodd@acm.org

 0
Chris
6/29/2004 12:00:42 AM
Similar Artilces:

LED strip / LED Linear Light for home and comercial use
Under developing, TECLED modular LED strip light / LED Linear Light - LED LiteBar 3 and LED LiteBar 5 will be anounced within 2 months. This system will be have two brightness choice as followed: LED LiteBar 3 come with 21 3528 high brightness SMD LED, output 150 lumens / foot, Each strip consume 1.8w electrical energy. Both LiteBar 3 and LiteBar 5 use 1mm thickness fiber glass PCB which have a good physical characteristics and good heat conduct performance. The LED strips / Bars can be cut every 3 LEDs segment. The cutting area will be indicated clearly. Both ends of strip have a intergrate...

[C++] using arrays in a class
/* I am trying to input names of 5 cities in a for loop, store them in an array, (not a vector as we havent got there yet), and then print them out. is this the correct way of doing it: [info doesnt seem to be doing much, am I using it correctly?] */ #include<iostream> #include<iomanip> #include<string> using namespace std; class Cities { private: string *city; public: Cities(); void input(); void output(); }; Cities:: Cities() { } void Cities::input() { int total=0; do{ cout<<"\n"; ...

Widget sets and what you use?
When you are creating a gui application do you tend to stick with the core Tk widgets or do you branch out (so to speak) with Bwidgets and the like? Which set do you like and why? I ask because, so far, I have stuck to the core Tk stuff. Oh, is there a tutorial using the other widget sets somewhere? I have the Welch (et al) book and that serves me for the core stuff. Robert "Robert" <sigzero@gmail.com> wrote in message news:BE19C60B.B0E5%sigzero@gmail.com... > When you are creating a gui application do you tend to stick with the core > Tk widgets or do you branch ...

DESIGN OF PID CONTROLLER FOR HIGHER ORDER CONTINUOUS SYSTEMS USING MPSOBASED MODEL FORMULATION TECHNIQUE
I need "design of PID controller for higher order systems using MPSO based model Formulation technique MATLAB source code" . Could any one send me the above code. Thank you. ...

using operator =; unsupported in msvc?
Since operator = is not inherited by default per C++ rules, I am trying to use the using keyword to bring it into scope. In gcc (g++) this works fine, but the msvc 6.0 compiler just ignores it and throws a compiler error when I try to use it. Consider the following code where I want to force inheritance of all operator = member functions from class base to class derived. This does not work in msvc 6.0 // CODE START #include <iostream> class base { public: base& operator = (int i) { m_i = i; return *this; } int m_i; }; cla...

Shifting
Hello Friends, I am new to MATLAB and I need to shift an image 5 pixel in x coordinate, and -10 pixels in y coordinate. what should I do? Any help Please? "Fariba Yousefi" <fariba_yoo@yahoo.co.uk> wrote in message <i8pho4$j48$1@fred.mathworks.com>... > Hello Friends, > I am new to MATLAB and I need to shift an image 5 pixel in x coordinate, and -10 pixels in y coordinate. > what should I do? Any help Please? Do you want to shift it in a circular manner, where the shifts cause wrap around? See >>doc circshift Wayne I searc...

am i using findNextSibling wrong?
i have this html: <td class="price"> <a class="nojs" name="D1L4" href="/xPopups/nojs" target="_blank">3.99</a> <div class="food">1.05</div> <div class="drink">3</div> <a class="btn" name="D1" href="http://www.cnn.com" target="_blank" onclick="reload()"> i tried to this use this python to scrape out the href cnn.com and failed. for incident in row('td', {'class'...

using shelve module to create web databases....problems?
I am finishing up a simple survey for a web site. I am creating a server-side data base using the shelve module. I am a relative python newcomer. I began with anydbm, but found that shelve uses anydbm and pickle so it is a bit easier for me to do what I want. The database I am testing list 4 candidates for president. A web form ( I use javascript to validate the data before sending it on ) posts the users survey data to a server-side python program which simply entesr the data into the database. The user can then go to another page to see the cumulative results of the survey. This is generate...

Unicode Vs. Shift-JIS
I have a friend that sends me notes from his Windows box and text utilties in Japanese. I think this/his enclave still uses Shift-JIS for some of their text encoding. I am of the suspicion that generally the Mac lives in unicode-ville. So he sends some text I can't read. Heretofore unable to convert them I scoured the net and found a text utility, really more a programmers environment like BBedit, called JEdit. It has an option to "Fix Garbled Text..." and let's you toggle the i/o, "What coding it is" and "what encoding I want". I was surprised...

[News] Linux Used to Build Another DVR
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 New 16-Channel H.264 Embedded Linux Standalone DVR for Business Security Camera Systems ,----[ Quote ] | We are proud to further expand our existing H.264 Standalone DVR product line | with the addition of our DVR-26416S 16-Channel Embedded Linux H.264 | Standalone DVR. This advanced remote viewable DVR is great for home or | business camera installs. ---- http://www.prlog.org/10178226-new-16-channel-h264-embedded-linux-standalone-dvr-for-business-security-camera-systems.html http://tinyurl.com/cg8ev3 Linux is kicking ass in this area. M...

problem with header margins when using fancyhdr

CL-YACC: Context-Dependent Precedence #2
Hi. Does CL-YACC have bison's context-dependent precedence such as: exp: ... | exp �-� exp ... | �-� exp %prec UMINUS If not, how could its absence be worked around? Norbert ...

Problems using kerberos with ssh.
Hello people, I configured kerberos in Linux using the defaults packages at Linux Fedora Core 1, the packages that i installed is krb5-libs ,krb5-workstation ,krb5-server and pam_krb5. This works perfectly when i telnet and normal logon but this doesnt work when i use it with ssh. I marked the option at sshd_config configuration file use the kerberos authentication but this doesnt work, sshd always prompt to login using /etc/passwd. What should i have to do to make it work? Will i have to install more packages?( i saw some people saying to use afs) Anyone here have ssh + kerberos wor...

Matrix element shifting or stacking
Hello, Any one can help me with this problem: I has this Matrix: NaN NaN NaN NaN 8 NaN NaN 7 8 NaN NaN 7 8 NaN NaN 7 8 NaN 6 7 8 9 NaN NaN 8 9 NaN NaN Which I need it to be like this: NaN NaN NaN NaN 8 7 NaN NaN 8 7 NaN NaN 8 7 NaN NaN 8 6 7 NaN 8 9 NaN NaN 8 9 NaN NaN I tried this code but it dose not give me the final results. % Shifting to lift for jj=size(STEP_Table_HOT,2)-1:-1:1 % from Right to Lift for ii=1:size(STEP_Table_HOT,1) if isnan(STEP_Table_HOT(ii,jj))==1 &&... isnan(STEP_Table_HOT(ii,jj+1))~=1 STEP_Table_HOT(ii,jj)=STEP_Tab...

Find shift between 2 star lists
Hello, I am new to IDL and I have the following task to complete and I cannot find an acceptable way to do it. I have 2 star lists of approximately the same field of stars. One list has about 100 stars and their locations (RA and DECLINATION) and the other list has about 10,000 stars and their location. The difference is that the second list is from observations that are much deeper than the first list. Both lists have different kind of information and the only common is the RA and DEC. I am trying to match the stars of the first list to the stars of the second list. I used match_...

Polygon count reduced after exporting mesh (??)
Hi, I'm having a strange problem for which I cannot find the cause. I'm exporting a scene as a VRML file. But when I import it again in 3dsMax, or in any other application, the number of faces is greatly reduced. For example, I have a flat floor in a room that is made out of many triangles so that no triangle is bigger than half a meter. But when I export the file the floor is made out of much less and larger faces that are stretched from one side of the room to the other. The shape of all geometry is still the same because the surface was flat anyway, but I badly ne...

That's what happens if you use Linux
<Quote> [Police seized] several computers, an iPod, a cell phone, and other technology [from student's dorm room at Boston U].... Some of the supposedly suspicious activities listed in support of the search warrant application include: the student being seen with "unknown laptop computers," which he "says" he was fixing for other students; the student uses multiple names to log on to his computer; and the student uses two different operating systems, including one that is not the "regular B.C. operating system" but instead has "a black screen with ...

Using MATLAB in-built qr in C++ #3
Hey All: I am trying to use MATLAB in-built qr using C++. The relevant code snippet is as follows: // Create input data double data[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}; mwArray in1(3, 5, mxDOUBLE_CLASS, mxREAL); mwArray in2(5, 3, mxDOUBLE_CLASS, mxREAL); in1.SetData(data, 15); in2.SetData(data, 15); //Show inputs. std::cout << "Input matrix 1 is:" << std::endl; std::cout << in1 << std::endl; std::cout << "Input matrix 2 is:" << std::endl; std::cout << in2 << std::endl; //Create output array mwArray out, out1, te...

What is the ';' use for?
Hi all, I understand by using the '[ ]', it is to define an array. May I know what is the ';' use for? commandchans = ['tmpchans = get(gcbf, ''userdata'');'... 'tmpchans = tmpchans{1};' ... 'set(findobj(gcbf, ''tag'', ''chantype''),''string'','... 'int2str(pop_chansel( tmpchans )));'... 'clear tmpchans;'] Thanks. ';' is used to delineate the end of a row of values. >> foo = [1 2 3; 4 5 6] foo = 1 2 3 4 5 6 But the exam...

Workaround for "use database" in a stored procedure
How can I get around the restriction of not being able to issue a "use database" statement in a stored procedure? I want to code a sybsystemprocs stored proc to: - set a database to single user mode - load the database - online the database - run some update statements in the database - disable single user mode The problem that I have is that I need to be in the database to issue the checkpoint after setting the database to single user, but I can't be in the database when the load statement is issued. I want to do this in a stored proc (or nested stored procs) ...

Default construction of arrays of PODs using new
I have what I think is a very simple question that everyone using C++ should know, yet I cannot find anywhere on the internet where it is answered, including the FAQ, and I have been using C++ for many years, and I don't know the answer for sure myself. That feels a bit embarrassing, but I guess it's just too long ago I used arrays instead of vector<X>. So now I am asking the question here. Consider this code: A* a = new A[10]; What I believe is that the 10 A's will be default-constructed if A is a non-POD type, while the default-constructor will not be called...

Using shc
Hello all, I'm using shc to compile some shell script I use for monitoring purpose on remote systems. I've a particular shell script that simply run a ps | grep to grep a process given as argument and exit as 0 if it's ok or 1 if it's not ok. This script runs from months on many systems (Linux 32/64bit, sunos 9, aix 5.3/6.1). I've compiled this script both on AIX and Linux. On AIX all is going ok. On Linux I've found that sometimes this script seems not to found requested process and obviously exit 1. I'm in doubt if can be a problem of compiled version or...

Using Units
I am stumbling through using units in Maple 15. I want to express a quantity as 30fT == 30femtotesla == 30*10^(-15)T I can do 30*10^(-15)T and manipulate it. How do I use prefixes like femto- (f)? Tom Dean "Thomas D. Dean" <tomdean@speakeasy.org> writes: > I am stumbling through using units in Maple 15. > > I want to express a quantity as 30fT == 30femtotesla == 30*10^(-15)T > > I can do 30*10^(-15)T and manipulate it. > > How do I use prefixes like femto- (f)? 30*Unit(fT); -- Joe Riel As Joe mentions, you can type in call...

Stamping multiple images without using ReusableStreamDecode filter
I need to print multiple scanned images stepped on a plate. If I use say: %%%%%%%%%%%%%%%%%%%begin example 4 dict dup /form exch def %%define dictionary as form /FormType 1 def /BBox [0 0 753 1019] def /Matrix [100100] def /Painproc { pop 14 14 translate 0 250 translate 180 -244 scale 753 1019 8 [753 0 0 1019 0 0] currentfile /ASCII85Decode filter /RunLengthDecode filter image %% iostream of image data from disk } bind def 10 10 translate form execform %% print once 753 0 translate form execform %% step 753 points from origin end %%%%%%%%%%%%%%%%%end example Now this works fine with useles...