Member Avatar for jpe4

I am currently doing a project on LR Parsers and need to code the algorithm using Java. The code should use the parse tables and determine wheather a word is accepted using the grammar provided and using the Parser tables. I am stuck on where to start so any advice on this would be very useful. Please can someone help me with this.

  • 3 Contributors
  • 2 Replies
  • 177 Views
  • 5 Years Discussion Span
  • Latest Post Latest Post by ddefrancesco
Member Avatar for BountyX

For others who don't know what an LR Parser is:

We show how LR parsers for the analysis of arbitrary context-free grammars can be derived from classical Earley's parsing algorithm. The result is a Generalized LR parsing algorithm working at complexity O(n3) in the worst case, which is achieved by the use of dynamic programming to represent the non-deterministic evolution of the stack instead of graph-structured stack representations, as has often been the case in previous approaches. The algorithm behave better in practical cases, achieving linear complexity on LR grammars. Experimental results show the performance of our proposal.

Source: http://coleweb.dc.fi.udc.es/cole/library/abstracts/AloCabVil97a.html

and

complexity O(n3) in the

is referring to big O notation.

with that said LR parsers can be easily expressed using recursive methods (*hint *hint) , without any use of automata theory.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.