[Mono-list] [PATCH] reduce shift/reduce conflicts
Simon Cozens
simon@simon-cozens.org
Fri, 13 Jul 2001 00:20:52 +0100
Please consider this very carefully, as I can't test it right now, and
apply selected hunks manually if appropriate.
I'm working on attacking the C# grammar to reduce the number of s/r
conflicts we see. (Not because jay does the wrong thing, but purely
out of cleanliness.)
Before patch:
yacc: 10 rules never reduced
yacc: 27 shift/reduce conflicts
After patch:
yacc: 14 shift/reduce conflicts
I've used C precedence for the operators to clean up some conflicts,
(can someone check that C's precendence is the same as C#s? I do *not*
guarantee that this patch creates correct grammars for C#, and I
currently can't test it.... :( ) and now *most* of the remaining ones
are due to recursive rules.
One of the hunks assumes we can hack the tokeniser to feed us
fully-qualified identifiers, which seems a safe bet. (I can provide a
patch for that if it's seen as a good idea.)
There's also some more general rearranging which either makes the
grammar easier to understand or removes some conflicts.
A typo I've just noticed, so not included in the patch:
Binary.Operator.Substract should be Binary.Operator.Subtract.
I'm not sure what we from with the grammar - if we want it to be
identical to the spec, it'll have conflicts and there's nothing we can
do about them. If we're prepared to be flexible for the purposes of
implementation, this'll help clean it up.
-----
Changelog entry:
2001-07-13 Simon Cozens <simon@netthink.co.uk>
* cs-parser.jay : Add operator precedence, remove some conflicts
-----
Patch:
--- cs-parser.orig Thu Jul 12 20:43:34 2001
+++ cs-parser.jay Fri Jul 13 00:16:21 2001
@@ -232,8 +232,25 @@
%token IDENTIFIER
/* Add precedence rules to solve dangling else s/r conflict */
+%nonassoc LOWPREC
%nonassoc IF
%nonassoc ELSE
+%left COMMA
+%right ASSIGN
+%left OP_OR
+%left OP_AND
+%left BITWISE_OR
+%left BITWISE_AND
+%left OP_SHIFT_LEFT OP_SHIFT_RIGHT
+%left PLUS MINUS
+%left STAR DIV PERCENT
+%right BANG CARRET UMINUS
+%nonassoc OP_INC OP_DEC
+%nonassoc CLOSE_PARENS
+%left OPEN_PARENS
+%left OPEN_BRACKET OPEN_BRACE
+%left DOT
+%nonassoc HIGHPREC
%start compilation_unit
/*%start namespace_declaration */
@@ -270,9 +287,11 @@
}
;
+/*
namespace_declarations
: namespace_declaration
| namespace_declarations namespace_declaration
+*/
namespace_declaration
: NAMESPACE qualified_identifier
@@ -296,9 +315,11 @@
;
qualified_identifier
- : IDENTIFIER
- | qualified_identifier DOT IDENTIFIER {
- $$ = (($1).ToString ()) + "." + ($3.ToString ()); }
+ : IDENTIFIER
+ /* | qualified_identifier DOT IDENTIFIER
+ { $$ = (($1).ToString ()) + "." + ($3.ToString ()); }
+ This will require a corresponding tokener hack.
+ */
;
@@ -369,16 +390,7 @@
//
opt_attributes
: /* empty */
- | attributes
- ;
-
-attributes
- : attribute_sections
- ;
-
-attribute_sections
- : attribute_section
- | attribute_sections attribute_section
+ | attribute_section opt_attributes
;
attribute_section
@@ -431,8 +443,9 @@
;
+/*
opt_dimension_separators
- : /* empty */
+ : // empty
| dimension_separators
;
@@ -440,6 +453,7 @@
: COMMA
| dimension_separators COMMA
;
+*/
class_body
: OPEN_BRACE opt_class_member_declarations CLOSE_BRACE
@@ -1176,11 +1190,7 @@
;
enum_body
- : OPEN_BRACE opt_enum_member_declarations CLOSE_BRACE
- {
- $$ = $2;
- }
- | OPEN_BRACE enum_member_declarations COMMA CLOSE_BRACE
+ : OPEN_BRACE opt_enum_member_declarations opt_comma CLOSE_BRACE
{
$$ = $2;
}
@@ -1522,7 +1532,7 @@
rank_specifiers
: rank_specifier
- | rank_specifiers rank_specifier
+ | rank_specifier rank_specifiers /* right recursion removes s/r conflict ??! */
// finishme
;
@@ -1550,8 +1560,7 @@
array_initializer
: OPEN_BRACE CLOSE_BRACE
- | OPEN_BRACE variable_initializer_list CLOSE_BRACE
- | OPEN_BRACE variable_initializer_list COMMA CLOSE_BRACE
+ | OPEN_BRACE variable_initializer_list opt_comma CLOSE_BRACE
// finishme
;
@@ -1610,9 +1619,16 @@
{
$$ = new Unary (Unary.Operator.AddressOf, (Expression) $2);
}
- | pre_increment_expression
- | pre_decrement_expression
- | cast_expression
+ | OP_INC unary_expression
+ {
+ $$ = new Unary (Unary.Operator.PreIncrement, (Expression) $2);
+ }
+ | OP_DEC unary_expression
+ {
+ $$ = new Unary (Unary.Operator.PreDecrement, (Expression) $2);
+ }
+ | OPEN_PARENS cast unary_expression
+ { $$ = new Cast ($2, (Expression) $3); }
/*
we can not do cast expressions at this level,
as there is an ambiguity. Check "Cast Expressions" 7.6.8
@@ -1634,19 +1650,10 @@
}
;
-cast_expression
- /* FIXME: This is actually wrong, it should be `type' but that
- * introduces a lot of {shift,reduce}/reduces
- */
- : OPEN_PARENS qualified_identifier CLOSE_PARENS unary_expression
- {
- $$ = new Cast (type ((string) $2), (Expression) $4);
- }
- | OPEN_PARENS builtin_types CLOSE_PARENS unary_expression
- {
- $$ = new Cast ((TypeRef) $2, (Expression) $4);
- }
- ;
+cast : qualified_identifier CLOSE_PARENS
+ { $$ = type ((string) $1); }
+ | builtin_types CLOSE_PARENS
+ { $$ = (TypeRef)$1; }
multiplicative_expression
: unary_expression
@@ -2414,11 +2421,11 @@
$$ = new Try ((Block) $2, s, (Catch) cc.Value, null);
}
- | TRY block finalize_clause
+ | TRY block FINALLY block
{
- $$ = new Try ((Block) $2, null, null, (Block) $3);
+ $$ = new Try ((Block) $2, null, null, (Block) $4);
}
- | TRY block catch_clauses finalize_clause
+ | TRY block catch_clauses FINALLY block
{
DictionaryEntry cc = (DictionaryEntry) $3;
ArrayList s = null;
@@ -2426,12 +2433,13 @@
if (cc.Key != null)
s = (ArrayList) cc.Key;
- $$ = new Try ((Block) $2, s, (Catch) cc.Value, (Block) $4);
+ $$ = new Try ((Block) $2, s, (Catch) cc.Value, (Block) $5);
}
;
+/* I'm not sure about this. Can it be Null? -SC */
catch_clauses
- : specific_catch_clauses opt_general_catch_clause
+ : specific_catch_clauses CATCH block
{
DictionaryEntry pair = new DictionaryEntry ();
@@ -2440,24 +2448,19 @@
$$ = pair;
}
- | opt_specific_catch_clauses general_catch_clause
+ | specific_catch_clauses
{
DictionaryEntry pair = new DictionaryEntry ();
- pair.Key = $1;
- pair.Value = $1;
+
+ pair.Key = $1;
+ pair.Value = Null;
$$ = pair;
}
- ;
-
-opt_general_catch_clause
- : /* empty */ { $$ = null; }
- | general_catch_clause
- ;
-
-opt_specific_catch_clauses
- : /* emtpy */ { $$ = null; }
- | specific_catch_clauses
+ | CATCH block
+ {
+ $$ = new Catch (null, null, (Block) $2);
+ }
;
specific_catch_clauses
@@ -2492,20 +2495,6 @@
opt_identifier
: /* empty */ { $$ = null; }
| IDENTIFIER
- ;
-
-general_catch_clause
- : CATCH block
- {
- $$ = new Catch (null, null, (Block) $2);
- }
- ;
-
-finalize_clause
- : FINALLY block
- {
- $$ = $2;
- }
;
checked_statement
--
Triage your efforts, y'know?
- Thorfinn