• Top
  • Documentation
  • Books
  • Boolean-reasoning
  • Projects
    • Apt
    • Acre
    • Milawa
    • Smtlink
    • Aleobft
    • Abnf
      • Deftreeops
      • Defdefparse
      • Defgrammar
      • Abnf-tree-utilities
      • Notation
      • Grammar-parser
        • Grammar-parser-implementation
          • Parse-grammar-from-file
          • Parse-ichar2
          • Parse-ichar
          • Parse-in-either-range
          • Parse-*-in-either-range
          • Parse-bit
          • Parse-equal-/-equal-slash
          • Parse-wsp
          • Parse-*digit-star-*digit
          • Parse-hexdig
          • Parse-cwsp
          • Parse-concatenation
          • Parse-case-insensitive-string
          • Parse-alpha
          • Parse-dot-1*bit
          • Parse-case-sensitive-string
          • Parse-bin/dec/hex-val
          • Parse-alpha/digit/dash
          • Parse-rule
          • Parse-repeat
          • Parse-cnl
          • Parse-sp
          • Parse-rule-/-*cwsp-cnl
          • Parse-element
          • Parse-dec-val
          • Parse-bin-val
          • Parse-alternation
          • Parse-*cwsp-cnl
          • Parse-*bit
          • Parse-wsp/vchar
          • Parse-quoted-string
          • Parse-prose-val
          • Parse-hex-val
          • Parse-grammar
          • Parse-elements
          • Parse-defined-as
          • Parse-dash-1*hexdig
          • Parse-comment
          • Parse-char-val
          • Parse-1*bit
          • Parse-rulename
          • Parse-num-val
          • Parse-htab
          • Parse-hex-val-rest
          • Parse-dot-1*hexdig
          • Parse-dot-1*digit
          • Parse-digit
          • Parse-dec-val-rest
          • Parse-dash-1*digit
          • Parse-dash-1*bit
          • Parse-crlf
          • Parse-cr
          • Parse-conc-rest-comp
          • Parse-cnl-wsp
          • Parse-bin-val-rest
          • Parse-alt-rest-comp
          • Parse-*cwsp
          • Parse-vchar
          • Parse-rulelist
          • Parse-option
          • Parse-group
          • Parse-1*-dot-1*hexdig
          • Parse-1*-dot-1*digit
          • Parse-1*-dot-1*bit
          • Parse-*-rule-/-*cwsp-cnl
          • Parse-*-alpha/digit/dash
          • Parse-lf
          • Parse-dquote
          • Parse-1*hexdig
          • Parse-1*cwsp
          • Parse-?repeat
          • Parse-*-dot-1*hexdig
          • Parse-*-dot-1*digit
          • Parse-*-dot-1*bit
          • Parse-repetition
          • Parse-1*digit
          • Parse-?%i
          • Parse-*wsp/vchar
          • Parse-*hexdig
          • Parse-*digit
          • Parse-alt-rest
          • Parse-conc-rest
          • *grammar-parser-error-msg*
        • Grammar-parser-correctness
      • Meta-circular-validation
      • Parsing-primitives-defresult
      • Parsing-primitives-seq
      • Operations
      • Examples
      • Differences-with-paper
      • Grammar-printer
      • Parsing-tools
    • Vwsim
    • Isar
    • Wp-gen
    • Dimacs-reader
    • Pfcs
    • Legacy-defrstobj
    • Proof-checker-array
    • Soft
    • Farray
    • Rp-rewriter
    • Instant-runoff-voting
    • Imp-language
    • Sidekick
    • Leftist-trees
    • C
    • Java
    • Taspi
    • Bitcoin
    • Des
    • Ethereum
    • X86isa
    • Sha-2
    • Yul
    • Riscv
    • Zcash
    • Proof-checker-itp13
    • Regex
    • ACL2-programming-language
    • Json
    • Jfkr
    • Equational
    • Cryptography
    • Poseidon
    • Where-do-i-place-my-book
    • Bigmems
    • Builtins
    • Axe
    • Execloader
    • Solidity
    • Leo
    • Paco
    • Concurrent-programs
  • Debugging
  • Std
  • Proof-automation
  • Macro-libraries
  • ACL2
  • Interfacing-tools
  • Hardware-verification
  • Software-verification
  • Math
  • Testing-utilities

• Grammar-parser-implementation

Parse-grammar

Parse a sequence of natural numbers into an ABNF grammar.

Signature

(parse-grammar nats) → tree?

Arguments

nats — Guard (nat-listp nats).

Returns

tree? — Type (tree-optionp tree?).

This function parses the natural numbers into a list of rules, returning the corresponding parse tree, or nil if parsing fails. This function also checks that there are no leftover natural numbers when parsing ends, returning nil if this check fails.

Definitions and Theorems

Function: parse-grammar

(defun parse-grammar (nats)
  (declare (xargs :guard (nat-listp nats)))
  (b* (((mv error? tree? rest)
        (parse-rulelist nats))
       ((when error?) nil)
       ((when rest) nil))
    tree?))

Theorem: tree-optionp-of-parse-grammar

(defthm tree-optionp-of-parse-grammar
  (b* ((tree? (parse-grammar nats)))
    (tree-optionp tree?))
  :rule-classes :rewrite)

Theorem: parse-grammar-of-nat-list-fix-nats

(defthm parse-grammar-of-nat-list-fix-nats
  (equal (parse-grammar (nat-list-fix nats))
         (parse-grammar nats)))

Theorem: parse-grammar-nat-list-equiv-congruence-on-nats

(defthm parse-grammar-nat-list-equiv-congruence-on-nats
  (implies (acl2::nat-list-equiv nats nats-equiv)
           (equal (parse-grammar nats)
                  (parse-grammar nats-equiv)))
  :rule-classes :congruence)