Resolving Conflicts

Overview

Often, grammars can contain ambiguities that ultimately result in conflicts. When conflicts occur during the construction of the LALR tables, they either take the form of shift-reduce or reduce-reduce errors. Currently, shift-reduce conflicts are resolved by selecting the "shift" action.

DFA conflicts are resolved by selecting the terminal that has a fixed length. These are most likely reserved words used in the grammar and typically have the same format as identifiers.

Parameter Approach

One possible solution is to add a number of parameters that the developer can use to specify how conflicts will be resolved.

The exact name and values of each still needs to be decided. However, the obvious "possible" values would include 'First Declared' and 'Last Declared'.

Rank Approach

The other approach would be to resolve conflicts by assigning a "rank" to each terminal and rule definition. When the system analyzes the grammar and constructs the Deterministic Finite Automata and the LALR State Table, conflicts could be resolved by simply selecting the higher-ranked object.

In the example above, the "If-Then-Else" rule has a higher rank. The system would then resolve the conflict by selecting it over the "If-Then" rule.   The notation used in the example is preliminary.

Whether #1 should be considered a higher rank than #2 or the other way around is still needed to be determined.

Compatibility

Rule Tags

Overview

It might be a great aid to developers if additional information can be saved along with each rule. This information would be passive and would not affect how the parse tables are constructed. However, this information could be useful to the developer implement their compiler or interpreter.

These "tags" could be stored in the "Reserved" field of the Compiled Grammar Table file. This would result in a new version of the GOLD CGT file format - version 1.1. Current implementations of the Engine should be able to read the updated file, but would not have access to the field. It is currently thrown away since it contains no information.

Numeric Tags

If the tag contains a numeric value, the developer could use it to specify enumerated constants independent of those generated by the Builder.  The notation used in the example below is preliminary.

Text Tags

Tags could also be stored as a string - giving more flexibility. In the example below, the developer has specified the text "If-Then".

However, there is the danger that tags could be used to to embed source code into the grammar. While this would follow the compiler-compiler paradigm, it would create language-dependent elements in grammars.

In either case, the information stored in the tag (and saved to the CGT), could be accessed through an object property or exported to the program template.

Compatibility

Includes & Namespacing

Overview

Suggested by Max Battcher. One possible change to the Meta-Language is adding "includes". Most programming languages contain the ability to add the source written in another module or file.

In C++, this is the #Include directive. Pascal and Delphi have a "uses" section.

Compatibility

Regular Expressions - Minimum & Maximum

Overview

Suggested by Don. POSIX uses an extended version of regular expressions that allows developers to specify the minimum and maximum number occurrences of a character group.

The notation conflicts with GOLD's notation for set literals. Any notation used in the Meta-language will have to modified so no conflicts exist.

Compatibility

Multiple Block Comments

Overview

Currently, most Engines use an internal "comment level" variable to determine when a the system is in "comment mode". When a block comment start terminal is read, the variable is incremented. While the variable is greater than or equal to one, the system will ignore all tokens and lexical errors. If a block comment end token is read, the variable is decremented by one.

This approach allows the system to easily handle the logic of block comments, but has one major drawback. Many programming languages, such as Pascal, have multiple block comments. In Pascal, the comment terminals must match. For instance, a (* must match a *)and a {  must match a }. Currently, GOLD cannot handle this logic.

Engine Changes

One approach would change how Engines handle block comments. Instead of using the single "comment level" variable, Engines would use an internal stack. Each time a Start Token is read, its symbol would be placed on a stack. If the stack has one or more items, the system would be in "comment mode".

When a End Token is read, the system would check if the top of the stack is the matching symbol. If it matches, the top of the stack would be discarded. If not, a "block comment mismatch" error must be reported.

CGT File Format Changes

The solution would require a modification of the CGT File Format. The Symbol Record in the Compiled Grammar Table file would require an additional field that contains the matching token for block comments. However, some problems can occur when the file is loaded.

Meta-language Changes

The changes to the Meta-language will be minor. The notation can be modified to to handle multiple block comments by adding a number to the Comment Start / End definition. The following is an example for Pascal:

Compatibility