bison - 尝试使用野牛为 DirectX x 格式的子集制作语法的移位/减少冲突

Question

我正在尝试为bison中的x格式提出一个语法（实际上是blender python脚本导出的子集的一个子集）。但是我正在减少冲突，Bison不会告诉我在哪里，或者“有点”告诉我在哪里，这取决于我尝试什么。

首先，这是来自搅拌机的示例 .x 文件，这是我正在测试的：

xof 0303txt 0032

Frame Root {
  FrameTransformMatrix {
     1.000000, 0.000000, 0.000000, 0.000000,
     0.000000, 0.000000, 1.000000, 0.000000,
     0.000000, 1.000000,-0.000000, 0.000000,
     0.000000, 0.000000, 0.000000, 1.000000;;
  }
  Frame Cube {
    FrameTransformMatrix {
       1.000000, 0.000000, 0.000000, 0.000000,
       0.000000, 1.000000, 0.000000, 0.000000,
       0.000000, 0.000000, 1.000000, 0.000000,
       0.000000, 0.000000, 0.000000, 1.000000;;
    }
    Mesh { //Cube_002 Mesh
      36;
      -1.000000;-1.000000;-1.000000;,
       1.000000;-1.000000;-1.000000;,
       1.000000; 1.000000;-1.000000;,
       0.999999;-1.000001; 1.000000;,
      -1.000000; 1.000000; 1.000000;,
       1.000000; 0.999999; 1.000000;,
       1.000000;-1.000000;-1.000000;,
       1.000000; 0.999999; 1.000000;,
       1.000000; 1.000000;-1.000000;,
      -1.000000;-1.000000;-1.000000;,
       0.999999;-1.000001; 1.000000;,
       1.000000;-1.000000;-1.000000;,
      -1.000000; 1.000000; 1.000000;,
      -1.000000;-1.000000; 1.000000;,
      -1.000000;-1.000000;-1.000000;,
      -1.000000; 1.000000;-1.000000;,
       1.000000; 1.000000;-1.000000;,
       1.000000; 0.999999; 1.000000;,
      -1.000000;-1.000000;-1.000000;,
       1.000000; 1.000000;-1.000000;,
      -1.000000; 1.000000;-1.000000;,
       0.999999;-1.000001; 1.000000;,
      -1.000000;-1.000000; 1.000000;,
      -1.000000; 1.000000; 1.000000;,
       1.000000;-1.000000;-1.000000;,
       0.999999;-1.000001; 1.000000;,
       1.000000; 0.999999; 1.000000;,
      -1.000000;-1.000000;-1.000000;,
      -1.000000;-1.000000; 1.000000;,
       0.999999;-1.000001; 1.000000;,
      -1.000000; 1.000000; 1.000000;,
      -1.000000;-1.000000;-1.000000;,
      -1.000000; 1.000000;-1.000000;,
      -1.000000; 1.000000;-1.000000;,
       1.000000; 0.999999; 1.000000;,
      -1.000000; 1.000000; 1.000000;;
      12;
      3;0;1;2;,
      3;3;4;5;,
      3;6;7;8;,
      3;9;10;11;,
      3;12;13;14;,
      3;15;16;17;,
      3;18;19;20;,
      3;21;22;23;,
      3;24;25;26;,
      3;27;28;29;,
      3;30;31;32;,
      3;33;34;35;;
      MeshNormals { //Cube_002 Normals
        36;
         0.000000; 0.000000;-1.000000;,
         0.000000; 0.000000;-1.000000;,
         0.000000; 0.000000;-1.000000;,
        -0.000000;-0.000000; 1.000000;,
        -0.000000;-0.000000; 1.000000;,
        -0.000000;-0.000000; 1.000000;,
         1.000000; 0.000000;-0.000000;,
         1.000000; 0.000000;-0.000000;,
         1.000000; 0.000000;-0.000000;,
        -0.000000;-1.000000;-0.000000;,
        -0.000000;-1.000000;-0.000000;,
        -0.000000;-1.000000;-0.000000;,
        -1.000000; 0.000000;-0.000000;,
        -1.000000; 0.000000;-0.000000;,
        -1.000000; 0.000000;-0.000000;,
         0.000000; 1.000000; 0.000000;,
         0.000000; 1.000000; 0.000000;,
         0.000000; 1.000000; 0.000000;,
         0.000000; 0.000000;-1.000000;,
         0.000000; 0.000000;-1.000000;,
         0.000000; 0.000000;-1.000000;,
         0.000000;-0.000000; 1.000000;,
         0.000000;-0.000000; 1.000000;,
         0.000000;-0.000000; 1.000000;,
         1.000000;-0.000001; 0.000000;,
         1.000000;-0.000001; 0.000000;,
         1.000000;-0.000001; 0.000000;,
        -0.000000;-1.000000; 0.000000;,
        -0.000000;-1.000000; 0.000000;,
        -0.000000;-1.000000; 0.000000;,
        -1.000000; 0.000000;-0.000000;,
        -1.000000; 0.000000;-0.000000;,
        -1.000000; 0.000000;-0.000000;,
         0.000000; 1.000000; 0.000000;,
         0.000000; 1.000000; 0.000000;,
         0.000000; 1.000000; 0.000000;;
        12;
        3;0;1;2;,
        3;3;4;5;,
        3;6;7;8;,
        3;9;10;11;,
        3;12;13;14;,
        3;15;16;17;,
        3;18;19;20;,
        3;21;22;23;,
        3;24;25;26;,
        3;27;28;29;,
        3;30;31;32;,
        3;33;34;35;;
      } //End of Cube_002 Normals
      MeshMaterialList { //Cube_002 Material List
        1;
        12;
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0;;
        Material Material {
           0.640000; 0.640000; 0.640000; 1.000000;;
           96.078431;
           0.500000; 0.500000; 0.500000;;
           0.000000; 0.000000; 0.000000;;
        }
      } //End of Cube_002 Material List
    } //End of Cube_002 Mesh
  } //End of Cube
} //End of Root Frame

以下是捕获语法的 2 次尝试：

有了这个，我得到：../XGrammar.y: conflicts: 1 shift/reduce

//----------------------------------------------------
Start
: KEYWORD ID '{' EntityDeclaration '}' END
;
//----------------------------------------------------
EntityDeclaration
: KEYWORD ID '{'AttributeDeclaration'}' EntityDeclaration
| KEYWORD ID '{'AttributeDeclaration'}'

;
//----------------------------------------------------
AttributeDeclaration
: KEYWORD  '{' Statement AttributeDeclaration '}' AttributeDeclaration
| KEYWORD  '{' Statement '}' AttributeDeclaration
| KEYWORD  '{' Statement AttributeDeclaration '}'
| KEYWORD  '{' Statement '}'
;
//----------------------------------------------------
Statement
: ExpressionList ';'
| ExpressionList ';' Statement
;
//----------------------------------------------------
ExpressionList
: Expression
| Expression ',' ExpressionList
;
//----------------------------------------------------
Expression
: INTEGER
| REAL
| VecFType
;
//----------------------------------------------------
VecFType
: Vec3FType
| Vec4FType
;
//----------------------------------------------------
Vec3FType
: REAL ';' REAL ';' REAL ';'
;
//----------------------------------------------------
Vec4FType
: REAL ';' REAL ';' REAL ';' REAL ';'
;

接下来，我得到：

../XGrammar.y: conflicts: 1 shift/reduce, 2 reduce/reduce
../XGrammar.y:56.3-9: warning: rule never reduced because of conflicts: Expression: Element

//----------------------------------------------------
Start
: KEYWORD ID '{' EntityDeclaration '}' END
;
//----------------------------------------------------
EntityDeclaration
: KEYWORD ID '{'AttributeDeclaration'}' EntityDeclaration
| KEYWORD ID '{'AttributeDeclaration'}'

;
//----------------------------------------------------
AttributeDeclaration
: KEYWORD  '{' Statement AttributeDeclaration '}' AttributeDeclaration
| KEYWORD  '{' Statement '}' AttributeDeclaration
| KEYWORD  '{' Statement AttributeDeclaration '}'
| KEYWORD  '{' Statement '}'
;
//----------------------------------------------------
Statement
: Expression ';'
| Expression ';' Statement
;
//----------------------------------------------------
Expression
: Container
| Element
;
//----------------------------------------------------
Container
: VecFType
| ArrayType
;
//----------------------------------------------------
ArrayType
: ';'
| Element ArrayElement
;
//----------------------------------------------------
ArrayElement
: ArrayType
| ','Element ArrayElement
;
//----------------------------------------------------
Element
: INTEGER
| REAL
;
//----------------------------------------------------
VecFType
: ';'
| Element VecElement
;

VecElement
: VecFType
| ';'Element VecElement
;

我对语法非常生疏（自大学以来已经有一段时间了），但我怀疑这与微软决定推出“容器”概念并将其与逗号和分号混合在一起的美妙方式有关：http ://msdn.microsoft.com/en-us/library/windows/desktop/bb206298(v=vs.85).aspx

他们说，基本上，一个容器是一种“隐式”，它的结尾用分号标记。这也恰好是它们标记数组结尾的方式，并且也恰好是在数组上下文中标记（显然）隐含容器的各个元素的方式......：S所以整个事情是狗屎秀。

首先，这种 x 格式不是 LR(1)。

不过，在重新阅读微软文档之后，我认为整个向量与数组的东西是 bs ......（我通过我的语法解释了这些类型之间的差异）。所以我想，我只需要为“Container”创建一个产品。大致如下：大括号部分中有两种类型的声明，独立的/范围内的/本地的/whathaveyou 和包含的。包含的类型与其他类型相同，只是在末尾带有一个额外的分号以“关闭”容器。但是，如果您查看 Microsoft 文档，您会发现它不一定是那样的。

第三种方法，我得到：

../XGrammar.y: conflicts: 4 shift/reduce, 1 reduce/reduce
../XGrammar.y:61.3-29: warning: rule never reduced because of conflicts: ContainerType: ',' Statement ContainerType


//----------------------------------------------------
Start
: KEYWORD ID '{' Entity '}' END
;
//----------------------------------------------------
Entity
: KEYWORD ID '{'Attribute'}' Entity
| KEYWORD ID '{'Attribute'}'

;
//----------------------------------------------------
Attribute
: KEYWORD  '{' Statement Attribute '}' Attribute
| KEYWORD  '{' Statement '}' Attribute
| KEYWORD  '{' Statement Attribute '}'
| KEYWORD  '{' Statement '}'
;
//----------------------------------------------------
Statement
: Declaration ';'
| Declaration ';' Statement
;

Declaration
: ElementType
| ContainerType
;

ContainerType
: Statement ',' Statement
| ',' Statement ContainerType
;
//----------------------------------------------------
ElementType
: INTEGER
| REAL
;
//----------------------------------------------------

所以我迷路了。任何帮助表示赞赏。

Answer 1

根据 Chris Dodd 的隐含回答，我得出的结论是，关键问题是，如前所述，X 格式无法以上下文无关语言捕获。这是因为分号（以非互斥方式）的怪异（抱歉，任意）使用

• 陈述
• 当数组在本地范围内声明时数组结束
• 如果元素属于隐含模板，则元素在数组中
• 隐含模板中的任何单个元素

只是让它无法提出无上下文的生产规则。

底线：从声明的角度解析所有内容，并在完成派生时根据当前令牌值分配语义。

我的新“语法”是：

//----------------------------------------------------
Start
: DeclarationList END
;
//----------------------------------------------------
DeclarationList
: Declaration DeclarationList
| Declaration
;
//----------------------------------------------------
Declaration
: Object
| Element
| ElementList
;
//----------------------------------------------------
Object
: KEYWORD ID '{' DeclarationList '}'
| KEYWORD '{' DeclarationList '}'
;
//----------------------------------------------------
ElementList
: Element ',' Element Ep
;
//----------------------------------------------------
Ep
: ',' Element Ep
|
;
//----------------------------------------------------
Element
: STRING
| INTEGER
| REAL
;

请注意，我仍然找到了一种将逗号与一个 lambda 产生式保持在一起的方法，以便提出“列表”的半截概念（这对于我赋予正在解析的数据的最终语义很有用）。

Answer 2

;在这些文件中使用和使用的完全随机方式,将导致我尝试通过完全忽略;/来解析它们,——例如：

input: input item | item ;
item: NUMBER | idlist '{' input '}' ;
idlist: idlist ID | ID ;

{}然后根据之前的关键字拆分每个 - 封闭块的内容。如果它是一个 WhatMatrix，那么它应该是 16 个数字。AMesh看起来是一个计数，后跟 3*count 坐标，然后是...

理解事物将完全取决于理解所有关键字的含义。