![编辑](https://linux22.com/image/232556/%E7%BC%96%E8%BE%91.png)
答案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
是n
ASCII 字符。如果 的代码点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
。上下文敏感性来自于使用每个标记后动态采取行动。