BNF (EBNF) 用可选列来描述 table 格式

Question

我正在尝试定义可用于描述以下类型 table 的语法：

**co1......**col2.......**col3......

价值.......价值.......价值

.....

其中 **col1 和 **col2 是列名。该格式可以选择具有其他预定义的列（例如，假设也可以包括 **col4 和 **col5）。我想编写一个输出这种格式的解析器。这种table可以用BNF或者EBNF来描述吗？

从我目前所读的内容来看，这是一个上下文相关的语法，因此不能用 BNF 或 EBNF 来描述（我假设这是因为如果 x-1 这样做，则行 x 将只包含 **col4出色地）。这个对吗？是否有任何替代方法来描述上面的 table 格式？

Answer 1

如果您的变量数大于两列且必须具有相同条目数，或者变量数大于两行且必须具有相同条目数，则该语言不能是上下文无关的出于同样的原因 a^n b^n c^n 不是上下文无关的。

如果你想要一个不受限制的表语法，像这样的东西会起作用：

// begin with A^n B
  S := AS | AB

// produce C^n D^n B
  A := CD               
 DC := CD

// produce C^n . E^n B
 DB := BE
CBE := C.EB
 BE := EB

// produce C^n . E^n G^n B
  E := EG
 GE := EG

// produce C^n (. E^n)+ B
 GB := BE
EBE := E.EB
 BE := EB

// produce C^n (. E^n)+
  B := (empty)

// lead column headings and values to terminal symbols
  C := (rules for headers)
  E := (rules for values)

为简单起见，以上假设所有值都是一种类型；也就是说，所有值都可以使用 E 的规则生成。如果要添加多个类型并与涉及的列进行协调，语法会变得复杂（需要E、E'、E''等，每个值类型一个，并且对应 G、G'、G'' 等和 C、C'、C'' 等，并复制产生式以处理移动 B 围绕每一个，但除此之外过程保持相似；然后你的语法将只生成具有正确类型匹配的表）。

BNF (EBNF) 用可选列来描述 table 格式

BNF (EBNF) to describe table format with optional columns

context-free-grammar

bnf

ebnf

context-sensitive-grammar