在定义 BNF 样式定义之前使用标识符

Question

在定义 BNF 语法时，通常在定义它们之前先使用一些东西，以便语法读取 "forwards."

如何在 coq 中执行此操作并且仍然能够遍历缓冲区？

Answer 1

在 Coq 中，buffer 的概念没有预先定义，所以很难理解你的意思。 Coq 仍然有两个方面给人一种可能的前瞻性感觉，可以在定义 BNF 语法时使用。

递归函数定义可以同时引入多个递归函数。
类型定义可以同时引入多个归纳类型。

在这两种情况下，第一个被定义的对象可以在定义之前引用第二个对象。

这里有两个例子，第一个是关于递归函数的。

Fixpoint even (n : nat) : bool :=
   match n with
     0 => true
   | S p => negb( odd p)
   end
with odd (n : nat) : bool :=
  match n with
    0 => false
  | S p => negb (even p)
  end.

您在这个例子中看到，函数 even 在定义之前引用了函数 odd。

现在是第二个例子。我试着坚持你对 BNF 的领先比喻。语法描述可以作为归纳谓词给出。这是一个小示例，其中包含仅涉及加法、乘法和自然数的算术表达式的语法。

Require Import String Ascii Arith.

Definition digit (c : ascii) : bool :=
  (nat_of_ascii "0" <=? nat_of_ascii c) &&
  (nat_of_ascii c <=? nat_of_ascii "9").

Fixpoint number (s : string) : bool :=
  match s with
  | String c EmptyString => digit c
  | String c tl => digit c && number tl
  | EmptyString => false
  end.

Inductive Exp1 : string -> Prop :=
  plus : forall x y, Exp2 x -> Exp1 y -> Exp1 (x ++ "+" ++ y)
| inj2 : forall x, Exp2 x -> Exp1 x
with
  Exp2 : string -> Prop :=
  times : forall x y, Exp3 x -> Exp2 y -> Exp2 (x ++ "*" ++ y)
| inj3 : forall x, Exp3 x -> Exp2 x
with
  Exp3 : string -> Prop :=
|  num : forall x, number x = true -> Exp3 x
|  inj1 : forall x, Exp1 x -> Exp3 ("(" ++ x ++ ")").

通过对语法的描述，我可以证明给定的表达式符合语法。

Lemma example : Exp1 "3+2*(5*4)".
Proof.
apply (plus "3" "2*(5*4)").
  apply inj3.
  apply num; reflexivity.
apply inj2.
apply (times "2" "(5*4)").
  apply num; reflexivity.
apply inj3, (inj1 "5*4"), inj2, (times "5" "4").
  apply num; reflexivity.
apply inj3, num; reflexivity.
Qed.

这不描述解析器。这将是另一个练习。

你的问题太简洁了，我什至不知道这是否是一个答案。

在定义 BNF 样式定义之前使用标识符

Use Identifier before Defining for BNF-Style Definitions

coq