Java Doc for lalr_state.java in  » Parser » CUP-develop » java_cup » Java Source Code / Java DocumentationJava Source Code and Java Documentation

Java Source Code / Java Documentation
1. 6.0 JDK Core
2. 6.0 JDK Modules
3. 6.0 JDK Modules com.sun
4. 6.0 JDK Modules com.sun.java
5. 6.0 JDK Modules sun
6. 6.0 JDK Platform
7. Ajax
8. Apache Harmony Java SE
9. Aspect oriented
10. Authentication Authorization
11. Blogger System
12. Build
13. Byte Code
14. Cache
15. Chart
16. Chat
17. Code Analyzer
18. Collaboration
19. Content Management System
20. Database Client
21. Database DBMS
22. Database JDBC Connection Pool
23. Database ORM
24. Development
25. EJB Server geronimo
26. EJB Server GlassFish
27. EJB Server JBoss 4.2.1
28. EJB Server resin 3.1.5
29. ERP CRM Financial
30. ESB
31. Forum
32. GIS
33. Graphic Library
34. Groupware
35. HTML Parser
36. IDE
37. IDE Eclipse
38. IDE Netbeans
39. Installer
40. Internationalization Localization
41. Inversion of Control
42. Issue Tracking
43. J2EE
44. JBoss
45. JMS
46. JMX
47. Library
48. Mail Clients
49. Net
50. Parser
51. PDF
52. Portal
53. Profiler
54. Project Management
55. Report
56. RSS RDF
57. Rule Engine
58. Science
59. Scripting
60. Search Engine
61. Security
62. Sevlet Container
63. Source Control
64. Swing Library
65. Template Engine
66. Test Coverage
67. Testing
68. UML
69. Web Crawler
70. Web Framework
71. Web Mail
72. Web Server
73. Web Services
74. Web Services apache cxf 2.0.1
75. Web Services AXIS2
76. Wiki Engine
77. Workflow Engines
78. XML
79. XML UI
Java
Java Tutorial
Java Open Source
Jar File Download
Java Articles
Java Products
Java by API
Photoshop Tutorials
Maya Tutorials
Flash Tutorials
3ds-Max Tutorials
Illustrator Tutorials
GIMP Tutorials
C# / C Sharp
C# / CSharp Tutorial
C# / CSharp Open Source
ASP.Net
ASP.NET Tutorial
JavaScript DHTML
JavaScript Tutorial
JavaScript Reference
HTML / CSS
HTML CSS Reference
C / ANSI-C
C Tutorial
C++
C++ Tutorial
Ruby
PHP
Python
Python Tutorial
Python Open Source
SQL Server / T-SQL
SQL Server / T-SQL Tutorial
Oracle PL / SQL
Oracle PL/SQL Tutorial
PostgreSQL
SQL / MySQL
MySQL Tutorial
VB.Net
VB.Net Tutorial
Flash / Flex / ActionScript
VBA / Excel / Access / Word
XML
XML Tutorial
Microsoft Office PowerPoint 2007 Tutorial
Microsoft Office Excel 2007 Tutorial
Microsoft Office Word 2007 Tutorial
Java Source Code / Java Documentation » Parser » CUP develop » java_cup 
Source Cross Reference  Class Diagram Java Document (Java Doc) 


java.lang.Object
   java_cup.lalr_state

lalr_state
public class lalr_state (Code)
This class represents a state in the LALR viable prefix recognition machine. A state consists of an LALR item set and a set of transitions to other states under terminal and non-terminal symbols. Each state represents a potential configuration of the parser. If the item set of a state includes an item such as:
 [A ::= B * C d E , {a,b,c}]
 
this indicates that when the parser is in this state it is currently looking for an A of the given form, has already seen the B, and would expect to see an a, b, or c after this sequence is complete. Note that the parser is normally looking for several things at once (represented by several items). In our example above, the state would also include items such as:
 [C ::= * X e Z, {d}]
 [X ::= * f, {e}]
 
to indicate that it was currently looking for a C followed by a d (which would be reduced into a C, matching the first symbol in our production above), and the terminal f followed by e.

At runtime, the parser uses a viable prefix recognition machine made up of these states to parse. The parser has two operations, shift and reduce. In a shift, it consumes one Symbol and makes a transition to a new state. This corresponds to "moving the dot past" a terminal in one or more items in the state (these new shifted items will then be found in the state at the end of the transition). For a reduce operation, the parser is signifying that it is recognizing the RHS of some production. To do this it first "backs up" by popping a stack of previously saved states. It pops off the same number of states as are found in the RHS of the production. This leaves the machine in the same state is was in when the parser first attempted to find the RHS. From this state it makes a transition based on the non-terminal on the LHS of the production. This corresponds to placing the parse in a configuration equivalent to having replaced all the symbols from the the input corresponding to the RHS with the symbol on the LHS.
See Also:   java_cup.lalr_item
See Also:   java_cup.lalr_item_set
See Also:   java_cup.lalr_transition
version:
   last updated: 7/3/96
author:
   Frank Flannery



Field Summary
protected static  Hashtable_all
     Collection of all states.
protected static  Hashtable_all_kernels
     Hash table to find states by their kernels (i.e, the original, unclosed, set of items -- which uniquely define the state).
protected  int_index
    
protected  lalr_item_set_items
     The item set for this state.
protected  lalr_transition_transitions
     List of transitions out of this state.
protected static  intnext_index
     Static counter for assigning unique state indexes.

Constructor Summary
public  lalr_state(lalr_item_set itms)
     Constructor for building a state from a set of items.

Method Summary
public  voidadd_transition(symbol on_sym, lalr_state to_st)
     Add a transition out of this state to another.
public static  Enumerationall()
     Collection of all states.
public static  lalr_statebuild_machine(production start_prod)
     Build an LALR viable prefix recognition machine given a start production.
public  voidbuild_table_entries(parse_action_table act_table, parse_reduce_table reduce_table)
     Fill in the parse table entries for this state.
public static  voidclear()
    
protected static  voiddump_state(lalr_state st)
     Helper routine for debugging -- produces a dump of the given state onto System.out.
public  booleanequals(lalr_state other)
     Equality comparison.
public  booleanequals(Object other)
     Generic equality comparison.
public static  lalr_statefind_state(lalr_item_set itms)
     Find and return state with a given a kernel item set (or null if not found).
protected  booleanfix_with_precedence(production p, int term_index, parse_action_row table_row, parse_action act)
     Procedure that attempts to fix a shift/reduce error by using precedences.
public  inthashCode()
     Produce a hash code.
public  intindex()
    
protected  parse_actioninsert_action(parse_action a1, parse_action a2, int act_type)
    
protected  parse_actioninsert_reduce(parse_action a1, parse_action a2)
    
protected  parse_actioninsert_shift(parse_action a1, parse_action a2)
    
public  lalr_item_setitems()
     The item set for this state.
public static  intnumber()
     Indicate total number of states there are.
protected static  voidpropagate_all_lookaheads()
     Propagate lookahead sets through the constructed viable prefix recognizer.
protected  voidpropagate_lookaheads()
     Propagate lookahead sets out of this state.
protected  voidreport_conflicts(terminal_set conflict_set)
     Produce warning messages for all conflicts found in this state.
protected  voidreport_reduce_reduce(lalr_item itm1, lalr_item itm2)
     Produce a warning message for one reduce/reduce conflict.
protected  voidreport_shift_reduce(lalr_item red_itm, int conflict_sym)
     Produce a warning message for one shift/reduce conflict.
public  StringtoString()
     Convert to a string.
public  lalr_transitiontransitions()
     List of transitions out of this state.

Field Detail
_all
protected static Hashtable _all(Code)
Collection of all states.



_all_kernels
protected static Hashtable _all_kernels(Code)
Hash table to find states by their kernels (i.e, the original, unclosed, set of items -- which uniquely define the state). This table stores state objects using (a copy of) their kernel item sets as keys.



_index
protected int _index(Code)
Index of this state in the parse tables



_items
protected lalr_item_set _items(Code)
The item set for this state.



_transitions
protected lalr_transition _transitions(Code)
List of transitions out of this state.



next_index
protected static int next_index(Code)
Static counter for assigning unique state indexes.




Constructor Detail
lalr_state
public lalr_state(lalr_item_set itms) throws internal_error(Code)
Constructor for building a state from a set of items.
Parameters:
  itms - the set of items that makes up this state.




Method Detail
add_transition
public void add_transition(symbol on_sym, lalr_state to_st) throws internal_error(Code)
Add a transition out of this state to another.
Parameters:
  on_sym - the symbol the transition is under.
Parameters:
  to_st - the state the transition goes to.



all
public static Enumeration all()(Code)
Collection of all states.



build_machine
public static lalr_state build_machine(production start_prod) throws internal_error(Code)
Build an LALR viable prefix recognition machine given a start production. This method operates by first building a start state from the start production (based on a single item with the dot at the beginning and EOF as expected lookahead). Then for each state it attempts to extend the machine by creating transitions out of the state to new or existing states. When considering extension from a state we make a transition on each symbol that appears before the dot in some item. For example, if we have the items:
 [A ::= a b * X c, {d,e}]
 [B ::= a b * X d, {a,b}]
 
in some state, then we would be making a transition under X to a new state. This new state would be formed by a "kernel" of items corresponding to moving the dot past the X. In this case:
 [A ::= a b X * c, {d,e}]
 [B ::= a b X * Y, {a,b}]
 
The full state would then be formed by "closing" this kernel set of items so that it included items that represented productions of things the parser was now looking for. In this case we would items corresponding to productions of Y, since various forms of Y are expected next when in this state (see lalr_item_set.compute_closure() for details on closure).

The process of building the viable prefix recognizer terminates when no new states can be added. However, in order to build a smaller number of states (i.e., corresponding to LALR rather than canonical LR) the state building process does not maintain full loookaheads in all items. Consequently, after the machine is built, we go back and propagate lookaheads through the constructed machine using a call to propagate_all_lookaheads(). This makes use of propagation links constructed during the closure and transition process.
Parameters:
  start_prod - the start production of the grammar
See Also:   java_cup.lalr_item_set.compute_closure
See Also:   java_cup.lalr_state.propagate_all_lookaheads




build_table_entries
public void build_table_entries(parse_action_table act_table, parse_reduce_table reduce_table) throws internal_error(Code)
Fill in the parse table entries for this state. There are two parse tables that encode the viable prefix recognition machine, an action table and a reduce-goto table. The rows in each table correspond to states of the machine. The columns of the action table are indexed by terminal symbols and correspond to either transitions out of the state (shift entries) or reductions from the state to some previous state saved on the stack (reduce entries). All entries in the action table that are not shifts or reduces, represent errors. The reduce-goto table is indexed by non terminals and represents transitions out of a state on that non-terminal.

Conflicts occur if more than one action needs to go in one entry of the action table (this cannot happen with the reduce-goto table). Conflicts are resolved by always shifting for shift/reduce conflicts and choosing the lowest numbered production (hence the one that appeared first in the specification) in reduce/reduce conflicts. All conflicts are reported and if more conflicts are detected than were declared by the user, code generation is aborted.
Parameters:
  act_table - the action table to put entries in.
Parameters:
  reduce_table - the reduce-goto table to put entries in.




clear
public static void clear()(Code)



dump_state
protected static void dump_state(lalr_state st) throws internal_error(Code)
Helper routine for debugging -- produces a dump of the given state onto System.out.



equals
public boolean equals(lalr_state other)(Code)
Equality comparison.



equals
public boolean equals(Object other)(Code)
Generic equality comparison.



find_state
public static lalr_state find_state(lalr_item_set itms)(Code)
Find and return state with a given a kernel item set (or null if not found). The kernel item set is the subset of items that were used to originally create the state. These items are formed by "shifting the dot" within items of other states that have a transition to this one. The remaining elements of this state's item set are added during closure.
Parameters:
  itms - the kernel set of the state we are looking for.



fix_with_precedence
protected boolean fix_with_precedence(production p, int term_index, parse_action_row table_row, parse_action act) throws internal_error(Code)
Procedure that attempts to fix a shift/reduce error by using precedences. --frankf 6/26/96 if a production (also called rule) or the lookahead terminal has a precedence, then the table can be fixed. if the rule has greater precedence than the terminal, a reduce by that rule in inserted in the table. If the terminal has a higher precedence, it is shifted. if they have equal precedence, then the associativity of the precedence is used to determine what to put in the table: if the precedence is left associative, the action is to reduce. if the precedence is right associative, the action is to shift. if the precedence is non associative, then it is a syntax error.
Parameters:
  p - the production
Parameters:
  term_index - the index of the lokahead terminal
Parameters:
  parse_action_row - a row of the action table
Parameters:
  act - the rule in conflict with the table entry



hashCode
public int hashCode()(Code)
Produce a hash code.



index
public int index()(Code)
Index of this state in the parse tables



insert_action
protected parse_action insert_action(parse_action a1, parse_action a2, int act_type) throws internal_error(Code)



insert_reduce
protected parse_action insert_reduce(parse_action a1, parse_action a2) throws internal_error(Code)



insert_shift
protected parse_action insert_shift(parse_action a1, parse_action a2) throws internal_error(Code)



items
public lalr_item_set items()(Code)
The item set for this state.



number
public static int number()(Code)
Indicate total number of states there are.



propagate_all_lookaheads
protected static void propagate_all_lookaheads() throws internal_error(Code)
Propagate lookahead sets through the constructed viable prefix recognizer. When the machine is constructed, each item that results in the creation of another such that its lookahead is included in the other's will have a propagate link set up for it. This allows additions to the lookahead of one item to be included in other items that it was used to directly or indirectly create.



propagate_lookaheads
protected void propagate_lookaheads() throws internal_error(Code)
Propagate lookahead sets out of this state. This recursively propagates to all items that have propagation links from some item in this state.



report_conflicts
protected void report_conflicts(terminal_set conflict_set) throws internal_error(Code)
Produce warning messages for all conflicts found in this state.



report_reduce_reduce
protected void report_reduce_reduce(lalr_item itm1, lalr_item itm2) throws internal_error(Code)
Produce a warning message for one reduce/reduce conflict.
Parameters:
  itm1 - first item in conflict.
Parameters:
  itm2 - second item in conflict.



report_shift_reduce
protected void report_shift_reduce(lalr_item red_itm, int conflict_sym) throws internal_error(Code)
Produce a warning message for one shift/reduce conflict.
Parameters:
  red_itm - the item with the reduce.
Parameters:
  conflict_sym - the index of the symbol conflict occurs under.



toString
public String toString()(Code)
Convert to a string.



transitions
public lalr_transition transitions()(Code)
List of transitions out of this state.



Methods inherited from java.lang.Object
native protected Object clone() throws CloneNotSupportedException(Code)(Java Doc)
public boolean equals(Object obj)(Code)(Java Doc)
protected void finalize() throws Throwable(Code)(Java Doc)
final native public Class getClass()(Code)(Java Doc)
native public int hashCode()(Code)(Java Doc)
final native public void notify()(Code)(Java Doc)
final native public void notifyAll()(Code)(Java Doc)
public String toString()(Code)(Java Doc)
final native public void wait(long timeout) throws InterruptedException(Code)(Java Doc)
final public void wait(long timeout, int nanos) throws InterruptedException(Code)(Java Doc)
final public void wait() throws InterruptedException(Code)(Java Doc)

www.java2java.com | Contact Us
Copyright 2009 - 12 Demo Source and Support. All rights reserved.
All other trademarks are property of their respective owners.