☰

编辑

tag-icon • tag-icon tex-core parsing grammar
编辑

我正在寻找 TeX 语言的 BNF 语法，它存在吗？

编辑

对于我们这些非计算机科学家来说，BNF 语法是 CFG 的一种形式化描述：巴科斯诺尔形式。

对于那些不了解乔姆斯基的人来说，CFG 是一个上下文无关文法，这意味着（非常粗略地）替换可以独立于其使用环境进行。

答案1

解析 TeX 是图灵完备的

TeX 只能由完整的图灵机（模数有限的可用空间）解析，这使得它无法拥有 BNF。这源于两个特性的结合：首先，TeX 是图灵完备的（如果你需要证明，这个图灵机模拟器就足够了）；其次，TeX 可以在运行时重新定义宏（及其解析规则）。由于 TeX 可以要求宏后面跟特定字符，因此重新定义宏可能意味着重新定义 TeX 的语法。结合这些事实，我们可以编写如下 TeX 代码，其中\f定义为某个任意（可计算）函数在 TeX 中的算法表示F：ℤ → ℤ：

\def\TuringCompleteness#1#2{%
  \edef\Output{#1{#2}}%
  \ifnum\Output=0
    \def\Required!{Bang!}%
  \else
    \def\Required?{Huh?}%
  \fi}
\TuringCompleteness{\f}{0}
\Required!

这个 TeX 能解析吗？这取决于F(0) / \f{0}! 而且由于 TeX 是图灵完备的，计算这个值可能需要一个完整的图灵机，因此也能确定它是否\Required!是有效的 TeX 语法。


情况变得更糟：类别代码

不过，也许您认为仍然可以对看起来像反斜杠、字母和括号内容的代码进行粗略检查。这很快就会变得不够，但这还不是全部。如果分隔宏还不够糟糕，那么当您意识到字符 、 、 、 等具有\其{行为}的原因$仅仅是因为 TeX 指定它们具有特定的“类别代码”时，情况会变得更糟。重新定义这些代码的能力意味着编写 TeX 就像

\catcode`\~=0
\catcode`\]=1
\catcode`\[=2
\catcode`\}=12
\catcode`\{=12
\catcode`\\=12

意味着所有随后的(La)TeX 代码必须像这样编写：

~textbf]This is bold-faced text.[  This text contains a literal backslash
(~texttt]\[) and literal curly braces (~texttt]{}[).

得到如下输出：

这是粗体文字。 此文本包含文字反斜杠 ( \) 和文字花括号 ( {})。


TeX 至少是上下文相关的建设性证明

此外，受到TH. 的回答，这里有一个具体的建设性证明，证明 TeX 不是上下文无关的。请注意，它不必依赖于 catcode 技巧——只需依赖 TeX 定义任意分隔宏的能力即可。（是的，第一节暗示了这一点，但看到一个具体案例仍然很好。）

\newcount\nesting

\def\RecognizeABC#1{\begingroup
  \nesting=0
  \OneStep#1\relax
  \ifnum\nesting=1
    There was \the\nesting\ copy of each control sequence.\par
  \else
    There were \the\nesting\ copies of each control sequence.\par
  \fi
\endgroup}

\def\CheckFinished#1{%
  \ifx#1\relax
    \def\OneStep#1{\relax}%
  \fi
  \OneStep#1}

\def\OneStep\a#1\b#2\c#3\relax{%
  \advance\nesting by 1
  \CheckFinished#1#2#3\relax}

此代码用于识别维基百科称之为“规范的非上下文无关语言”n副本\a随后n副本\b随后n副本\c，其中n至少为 1。第一行仅分配一个计数器；我们将使用它来跟踪我们看到的控制序列的副本数，但这只是为了在最后显示一些文本，而不是为了解析。要尝试识别某些文本，请调用 。这只是\RecognizeABC{...}将其设置\nesting为零（再次用于输出目的），然后调用\OneStep。 \OneStep设置为接受三个参数\a由、\b和分隔\c。第一个参数必须位于\a和之间\b，第二个参数位于\b和之间\c，第三个参数位于\c和 之间。如果、和\relax中每个参数的数量相同，那么最终将是，并且所有参数都将为空。对于，我们仅记录、和每个参数都多一个的事实（再次强调，这只是为了输出），然后查看是否完成。 查看输入流中的下一个标记是什么。如果是，则参数为空，并且完成；重新定义为不执行任何操作。现在，在剩余的输入流上调用 — 无论是解析宏还是什么都不做 — 并进行递归。完成后，我们终于完成，其中我们排版了我们看到的每个控制序列的副本数。\a\b\c\OneStep\a\b\c\relax\OneStep\a\b\c\CheckFinished\relax\OneStep\OneStep\RecognizeABC

呼！如果你没理解这些，那么如果我们只看重要的宏，那么跟踪结果如下所示：

[START] \RecognizeABC{\a\a\a\b\b\b\c\c\c}
    --> \OneStep\a\a\a\b\b\b\c\c\c\relax
                  -#1-  -#2-  -#3-
    --> \CheckFinished\a\a\b\b\c\c\relax
    --> \OneStep\a\a\b\b\c\c\relax
                  #1  #2  #3
    --> \CheckFinished\a\b\c\relax
    --> \OneStep\a\b\c\relax
          (All the arguments are empty.)
    --> \CheckFinished\relax
    --> ``There were 3 copies of each control sequence.''

因此，以下 TeX

\RecognizeABC{\a\b\c}
\RecognizeABC{\a\a\b\b\c\c}
\RecognizeABC{\a\a\a\b\b\b\c\c\c}

产生以下输出：

每个控制序列有 1 个拷贝。
每个控制序列有 2 个拷贝。
每个控制序列有 3 个拷贝。

但是 TeX 比如

\RecognizeABC{}
\RecognizeABC{\a}
\RecognizeABC{\a\a\b\b\c\c\c}
\RecognizeABC{\a\b\c\garbage}

失败。

编辑1：除了修复一些小错误/清理并将答案分成带有标题的部分之外，我还扩展了 TeX 无法被图灵机以外的任何东西解析的理由，希望能够让它更清楚一些。这涉及删除前面的示例\weird，用更像证明的东西代替它。如果你更愿意有一个具体的例子（但不是证据）用重新定义的命令本身，请考虑以下之前存在的 TeX：

\def\weird[#1][#2]{%
  \ifx#1\relax
    \def\weird!{I was previously called with a relaxing first argument.}%
  \else\ifx#2\relax
    \def\weird(##1){I can only be called with one argument; I was given (##1).}%
  \fi\fi
  I was called with [#1] and [#2].}

首先，\weird必须被调用为\weird[stuff][other stuff]。但如果它的第一个参数是\relax，那么它会重新定义自己，要求被调用为\weird!；如果它的第二个参数什么都没有，它会重新定义自己，要求被调用为\weird(stuff)；并且它总是排版文本。这不能被 BNF 语法捕获（我不认为）。当然，在一般情况下，我们需要一台图灵机。

答案2

TH. 和 Antal 的优秀帖子的另一个角度是，除了 TeX 是图灵完备机之外，它还可以被强制执行 lambda 演算，这是所有函数式语言的基础。在 CTAN 上有一个名为lambda 列表由 Alan Jeffrey 开发的，它实现了除其他 lambda 概念之外的无界列表。TeX 不仅做到了所有这些，而且令人印象深刻的是，这些例程是在 TeX 口中实现的，证明了TeX 的嘴与任何地方的任何计算机一样强大。

要理解 lambda 演算和图灵机之间的关系，需要参考判定问题这是大卫·希尔伯特提出的著名23个问题之一。

1936 年和 1937 年，阿隆佐·丘奇和阿兰·图灵分别发表了独立论文，表明不可能通过算法来判断算术语句的真假，因此不可能找到判定问题的一般解。

1936 年，阿隆佐·丘奇基于他的 λ 演算提出了“有效可计算性”的概念，同年，阿兰·图灵也提出了图灵机的概念。后来人们认识到，它们是等效的计算模型。两位作者的工作都深受库尔特·哥德尔早期关于不完备定理的工作的影响 - 维基百科

因此，lambda 演算、图灵机和 TeX 不仅密切相关，而且它们是等效的计算模型，这是 TeX 及其朋友有趣的众多方面之一！

答案3

这极不可能。TeX 可以在读取输入的过程中改变其解析输入的方式。我得再考虑一下，但我认为这会阻止 TeX 拥有上下文无关语法，因此它可能没有 BNF。

答案4

您可以随时查看原件源代码for TeX(LaTeX是基于 的扩展而构建的TeX)。它具有高度可读性（得益于其专有的 WEB 语言），并且实际上可以TeX使用 编译为可读文档weave（内置于大多数TeX发行版中）。

关于解析，这里是重要部分的总结（从最令人厌恶的事实到最不令人厌恶的事实）：

  • 在定义命令时，任何事物可以作为参数分隔符（注释可以正常工作，但间距会变得混乱）。例如，

    \def\test |\a#1@$^&^TRDFS(#2


|{5#1#25}

\test|\a {f}@$^&^TRDFS(f


| % This prints 5ff5

    TeX仅根据代码点和类别匹配参数（完全忽略宏定义）。这就是顶部答案的“建设性证明”奏效的原因。

  • ^^@与 ASCII 同义<null>...事实上，假设我们有^^n是nASCII 字符。如果 的代码点n小于 64，则加 64 并返回。否则，减 64 并返回。此外，^^XX与具有代码点的字符同义0xXX（十六进制）。

    • 更糟糕的是...\t^^65ste等于\tAste。您甚至可以\tAste使用 来定义\def\t^^65ste。
    • 幸运的是，参数分隔符中忽略了这一点（无注释）。

  • TeX对于不同的字母表来说，有一些上下文无关的组件。如果我们将TeX的字母表视为对，a:c其中a是 ASCII 字符，c是其（符号）类别代码，那么，例如，TeX数字（参见scan_int程序）可以按如下方式用 EBNF 写出

    decimal_number = ("+:other_char" | "-:other_char")* digit+
digit          = "0:other_char" | ... | "9:other_char"

  • 擦除语义，TeX具有仅使用类别代码的 (E)BNF。例如，

    control_sequence = escape (letter)*

    这正是lexer标记化 的确切方式TeX。上下文敏感性来自于使用每个标记后动态采取行动。

相关内容