Parse statements, blocks, and related entities.
This clique of mutually recursive functions shares some characteristics with the clique to parse expressions, declarations, and related entities. See parse-exprs/decls for a discussion of technicalities that also apply to this clique.
Function:
(defun parse-statement (pstate) (declare (xargs :guard (parstatep pstate))) (let ((__function__ 'parse-statement)) (declare (ignorable __function__)) (b* (((reterr) (irr-stmt) (irr-span) (irr-parstate)) ((erp token span pstate) (read-token pstate))) (cond ((and token (token-case token :ident)) (b* ((ident (token-ident->unwrap token)) ((erp token2 & pstate) (read-token pstate))) (cond ((equal token2 (token-punctuator ":")) (b* (((erp stmt last-span pstate) (parse-statement pstate))) (retok (make-stmt-labeled :label (label-name ident) :stmt stmt) (span-join span last-span) pstate))) (t (b* ((pstate (if token2 (unread-token pstate) pstate)) (pstate (unread-token pstate)) ((erp expr span pstate) (parse-expression pstate)) ((erp last-span pstate) (read-punctuator ";" pstate))) (retok (stmt-expr expr) (span-join span last-span) pstate)))))) ((equal token (token-punctuator "{")) (b* (((erp token2 span2 pstate) (read-token pstate))) (cond ((equal token2 (token-punctuator "}")) (retok (stmt-compound nil) (span-join span span2) pstate)) (t (b* ((pstate (if token2 (unread-token pstate) pstate)) ((erp items & pstate) (parse-block-item-list pstate)) ((erp last-span pstate) (read-punctuator "}" pstate))) (retok (stmt-compound items) (span-join span last-span) pstate)))))) ((equal token (token-punctuator ";")) (retok (stmt-expr nil) span pstate)) ((equal token (token-keyword "case")) (b* (((erp cexpr & pstate) (parse-constant-expression pstate)) ((erp & pstate) (read-punctuator ":" pstate)) ((erp stmt last-span pstate) (parse-statement pstate))) (retok (make-stmt-labeled :label (label-const cexpr) :stmt stmt) (span-join span last-span) pstate))) ((equal token (token-keyword "default")) (b* (((erp & pstate) (read-punctuator ":" pstate)) ((erp stmt last-span pstate) (parse-statement pstate))) (retok (make-stmt-labeled :label (label-default) :stmt stmt) (span-join span last-span) pstate))) ((equal token (token-keyword "goto")) (b* (((erp ident & pstate) (read-identifier pstate)) ((erp last-span pstate) (read-punctuator ";" pstate))) (retok (stmt-goto ident) (span-join span last-span) pstate))) ((equal token (token-keyword "continue")) (b* (((erp last-span pstate) (read-punctuator ";" pstate))) (retok (stmt-continue) (span-join span last-span) pstate))) ((equal token (token-keyword "break")) (b* (((erp last-span pstate) (read-punctuator ";" pstate))) (retok (stmt-break) (span-join span last-span) pstate))) ((equal token (token-keyword "return")) (b* (((erp token2 span2 pstate) (read-token pstate))) (cond ((token-expression-start-p token2) (b* ((pstate (unread-token pstate)) ((erp expr & pstate) (parse-expression pstate)) ((erp last-span pstate) (read-punctuator ";" pstate))) (retok (stmt-return expr) (span-join span last-span) pstate))) ((equal token2 (token-punctuator ";")) (retok (stmt-return nil) (span-join span span2) pstate)) (t (reterr-msg :where (position-to-msg (span->start span2)) :expected "an expression or a semicolon" :found (token-to-msg token2)))))) ((equal token (token-keyword "if")) (b* (((erp & pstate) (read-punctuator "(" pstate)) ((erp expr & pstate) (parse-expression pstate)) ((erp & pstate) (read-punctuator ")" pstate)) (psize (parsize pstate)) ((erp stmt stmt-span pstate) (parse-statement pstate)) ((unless (mbt (<= (parsize pstate) (1- psize)))) (reterr :impossible)) ((erp token2 & pstate) (read-token pstate))) (cond ((equal token2 (token-keyword "else")) (b* (((erp stmt-else last-span pstate) (parse-statement pstate))) (retok (make-stmt-ifelse :test expr :then stmt :else stmt-else) (span-join span last-span) pstate))) (t (b* ((pstate (if token2 (unread-token pstate) pstate))) (retok (make-stmt-if :test expr :then stmt) (span-join span stmt-span) pstate)))))) ((equal token (token-keyword "switch")) (b* (((erp & pstate) (read-punctuator "(" pstate)) ((erp expr & pstate) (parse-expression pstate)) ((erp & pstate) (read-punctuator ")" pstate)) ((erp stmt last-span pstate) (parse-statement pstate))) (retok (make-stmt-switch :target expr :body stmt) (span-join span last-span) pstate))) ((equal token (token-keyword "while")) (b* (((erp & pstate) (read-punctuator "(" pstate)) ((erp expr & pstate) (parse-expression pstate)) ((erp & pstate) (read-punctuator ")" pstate)) ((erp stmt last-span pstate) (parse-statement pstate))) (retok (make-stmt-while :test expr :body stmt) (span-join span last-span) pstate))) ((equal token (token-keyword "do")) (b* (((erp stmt & pstate) (parse-statement pstate)) ((erp & pstate) (read-keyword "while" pstate)) ((erp & pstate) (read-punctuator "(" pstate)) ((erp expr & pstate) (parse-expression pstate)) ((erp & pstate) (read-punctuator ")" pstate)) ((erp last-span pstate) (read-punctuator ";" pstate))) (retok (make-stmt-dowhile :body stmt :test expr) (span-join span last-span) pstate))) ((equal token (token-keyword "for")) (b* (((erp & pstate) (read-punctuator "(" pstate)) ((erp token2 & pstate) (read-token pstate))) (cond ((equal token2 (token-punctuator ";")) (b* (((erp token3 span3 pstate) (read-token pstate))) (cond ((token-expression-start-p token3) (b* ((pstate (unread-token pstate)) ((erp test-expr & pstate) (parse-expression pstate)) ((erp & pstate) (read-punctuator ";" pstate)) ((erp token4 span4 pstate) (read-token pstate))) (cond ((token-expression-start-p token4) (b* ((pstate (unread-token pstate)) ((erp next-expr & pstate) (parse-expression pstate)) ((erp & pstate) (read-punctuator ")" pstate)) ((erp stmt last-span pstate) (parse-statement pstate))) (retok (make-stmt-for-expr :init nil :test test-expr :next next-expr :body stmt) (span-join span last-span) pstate))) ((equal token4 (token-punctuator ")")) (b* (((erp stmt last-span pstate) (parse-statement pstate))) (retok (make-stmt-for-expr :init nil :test test-expr :next nil :body stmt) (span-join span last-span) pstate))) (t (reterr-msg :where (position-to-msg (span->start span4)) :expected "an expression ~ or a closed parenthesis" :found (token-to-msg token4)))))) ((equal token3 (token-punctuator ";")) (b* (((erp token4 span4 pstate) (read-token pstate))) (cond ((token-expression-start-p token4) (b* ((pstate (unread-token pstate)) ((erp next-expr & pstate) (parse-expression pstate)) ((erp & pstate) (read-punctuator ")" pstate)) ((erp stmt last-span pstate) (parse-statement pstate))) (retok (make-stmt-for-expr :init nil :test nil :next next-expr :body stmt) (span-join span last-span) pstate))) ((equal token4 (token-punctuator ")")) (b* (((erp stmt last-span pstate) (parse-statement pstate))) (retok (make-stmt-for-expr :init nil :test nil :next nil :body stmt) (span-join span last-span) pstate))) (t (reterr-msg :where (position-to-msg (span->start span4)) :expected "an expression ~ or a closed parenthesis" :found (token-to-msg token4)))))) (t (reterr-msg :where (position-to-msg (span->start span3)) :expected "an expression ~ or a semicolon" :found (token-to-msg token3)))))) (t (b* ((pstate (if token2 (unread-token pstate) pstate)) ((erp decl/stmt & pstate) (parse-declaration-or-statement pstate))) (amb?-decl/stmt-case decl/stmt :decl (b* ((decl (amb?-decl/stmt-decl->unwrap decl/stmt)) ((erp token3 span3 pstate) (read-token pstate))) (cond ((token-expression-start-p token3) (b* ((pstate (unread-token pstate)) ((erp test-expr & pstate) (parse-expression pstate)) ((erp & pstate) (read-punctuator ";" pstate)) ((erp token4 span4 pstate) (read-token pstate))) (cond ((token-expression-start-p token4) (b* ((pstate (unread-token pstate)) ((erp next-expr & pstate) (parse-expression pstate)) ((erp & pstate) (read-punctuator ")" pstate)) ((erp stmt last-span pstate) (parse-statement pstate))) (retok (make-stmt-for-decl :init decl :test test-expr :next next-expr :body stmt) (span-join span last-span) pstate))) ((equal token4 (token-punctuator ")")) (b* (((erp stmt last-span pstate) (parse-statement pstate))) (retok (make-stmt-for-decl :init decl :test test-expr :next nil :body stmt) (span-join span last-span) pstate))) (t (reterr-msg :where (position-to-msg (span->start span4)) :expected "an expression ~ or a closed parenthesis" :found (token-to-msg token4)))))) ((equal token3 (token-punctuator ";")) (b* (((erp token4 span4 pstate) (read-token pstate))) (cond ((token-expression-start-p token4) (b* ((pstate (unread-token pstate)) ((erp next-expr & pstate) (parse-expression pstate)) ((erp & pstate) (read-punctuator ")" pstate)) ((erp stmt last-span pstate) (parse-statement pstate))) (retok (make-stmt-for-decl :init decl :test nil :next next-expr :body stmt) (span-join span last-span) pstate))) ((equal token4 (token-punctuator ")")) (b* (((erp stmt last-span pstate) (parse-statement pstate))) (retok (make-stmt-for-decl :init decl :test nil :next nil :body stmt) (span-join span last-span) pstate))) (t (reterr-msg :where (position-to-msg (span->start span4)) :expected "an expression ~ or a closed parenthesis" :found (token-to-msg token4)))))) (t (reterr-msg :where (position-to-msg (span->start span3)) :expected "an expression ~ or a semicolon" :found (token-to-msg token3))))) :stmt (b* ((expr (amb?-decl/stmt-stmt->unwrap decl/stmt)) ((erp token3 span3 pstate) (read-token pstate))) (cond ((token-expression-start-p token3) (b* ((pstate (unread-token pstate)) ((erp test-expr & pstate) (parse-expression pstate)) ((erp & pstate) (read-punctuator ";" pstate)) ((erp token4 span4 pstate) (read-token pstate))) (cond ((token-expression-start-p token4) (b* ((pstate (unread-token pstate)) ((erp next-expr & pstate) (parse-expression pstate)) ((erp & pstate) (read-punctuator ")" pstate)) ((erp stmt last-span pstate) (parse-statement pstate))) (retok (make-stmt-for-expr :init expr :test test-expr :next next-expr :body stmt) (span-join span last-span) pstate))) ((equal token4 (token-punctuator ")")) (b* (((erp stmt last-span pstate) (parse-statement pstate))) (retok (make-stmt-for-expr :init expr :test test-expr :next nil :body stmt) (span-join span last-span) pstate))) (t (reterr-msg :where (position-to-msg (span->start span4)) :expected "an expression ~ or a closed parenthesis" :found (token-to-msg token4)))))) ((equal token3 (token-punctuator ";")) (b* (((erp token4 span4 pstate) (read-token pstate))) (cond ((token-expression-start-p token4) (b* ((pstate (unread-token pstate)) ((erp next-expr & pstate) (parse-expression pstate)) ((erp & pstate) (read-punctuator ")" pstate)) ((erp stmt last-span pstate) (parse-statement pstate))) (retok (make-stmt-for-expr :init expr :test nil :next next-expr :body stmt) (span-join span last-span) pstate))) ((equal token4 (token-punctuator ")")) (b* (((erp stmt last-span pstate) (parse-statement pstate))) (retok (make-stmt-for-expr :init expr :test nil :next nil :body stmt) (span-join span last-span) pstate))) (t (reterr-msg :where (position-to-msg (span->start span4)) :expected "an expression ~ or a closed parenthesis" :found (token-to-msg token4)))))) (t (reterr-msg :where (position-to-msg (span->start span3)) :expected "an expression ~ or a semicolon" :found (token-to-msg token3))))) :ambig (b* ((decl/expr (amb?-decl/stmt-ambig->unwrap decl/stmt)) ((erp token3 span3 pstate) (read-token pstate))) (cond ((token-expression-start-p token3) (b* ((pstate (unread-token pstate)) ((erp test-expr & pstate) (parse-expression pstate)) ((erp & pstate) (read-punctuator ";" pstate)) ((erp token4 span4 pstate) (read-token pstate))) (cond ((token-expression-start-p token4) (b* ((pstate (unread-token pstate)) ((erp next-expr & pstate) (parse-expression pstate)) ((erp & pstate) (read-punctuator ")" pstate)) ((erp stmt last-span pstate) (parse-statement pstate))) (retok (make-stmt-for-ambig :init decl/expr :test test-expr :next next-expr :body stmt) (span-join span last-span) pstate))) ((equal token4 (token-punctuator ")")) (b* (((erp stmt last-span pstate) (parse-statement pstate))) (retok (make-stmt-for-ambig :init decl/expr :test test-expr :next nil :body stmt) (span-join span last-span) pstate))) (t (reterr-msg :where (position-to-msg (span->start span4)) :expected "an expression ~ or a closed parenthesis" :found (token-to-msg token4)))))) ((equal token3 (token-punctuator ";")) (b* (((erp token4 span4 pstate) (read-token pstate))) (cond ((token-expression-start-p token4) (b* ((pstate (unread-token pstate)) ((erp next-expr & pstate) (parse-expression pstate)) ((erp & pstate) (read-punctuator ")" pstate)) ((erp stmt last-span pstate) (parse-statement pstate))) (retok (make-stmt-for-ambig :init decl/expr :test nil :next next-expr :body stmt) (span-join span last-span) pstate))) ((equal token4 (token-punctuator ")")) (b* (((erp stmt last-span pstate) (parse-statement pstate))) (retok (make-stmt-for-ambig :init decl/expr :test nil :next nil :body stmt) (span-join span last-span) pstate))) (t (reterr-msg :where (position-to-msg (span->start span4)) :expected "an expression ~ or a closed parenthesis" :found (token-to-msg token4)))))) (t (reterr-msg :where (position-to-msg (span->start span3)) :expected "an expression ~ or a semicolon" :found (token-to-msg token3))))))))))) ((token-expression-start-p token) (b* ((pstate (unread-token pstate)) ((erp expr span pstate) (parse-expression pstate)) ((erp last-span pstate) (read-punctuator ";" pstate))) (retok (stmt-expr expr) (span-join span last-span) pstate))) (t (reterr-msg :where (position-to-msg (span->start span)) :expected "an identifier ~ or a keyword in {~ break, ~ case, ~ continue, ~ default, ~ do, ~ for, ~ goto, ~ if, ~ return, ~ switch, ~ while~ } ~ or a punctuator in {~ \"++\", ~ \"--\", ~ \"+\", ~ \"-\", ~ \"~~\", ~ \"!\", ~ \"*\", ~ \"&\", ~ \"(\", ~ \"{\", ~ \";\"~ }" :found (token-to-msg token)))))))
Function:
(defun parse-block-item (pstate) (declare (xargs :guard (parstatep pstate))) (let ((__function__ 'parse-block-item)) (declare (ignorable __function__)) (b* (((reterr) (irr-block-item) (irr-span) (irr-parstate)) ((erp token & pstate) (read-token pstate))) (cond ((and token (token-case token :ident)) (b* ((pstate (unread-token pstate)) ((erp decl/stmt span pstate) (parse-declaration-or-statement pstate))) (amb?-decl/stmt-case decl/stmt :decl (retok (block-item-decl decl/stmt.unwrap) span pstate) :stmt (retok (block-item-stmt (stmt-expr decl/stmt.unwrap)) span pstate) :ambig (retok (block-item-ambig decl/stmt.unwrap) span pstate)))) ((token-declaration-specifier-start-p token) (b* ((pstate (unread-token pstate)) ((erp decl span pstate) (parse-declaration pstate))) (retok (block-item-decl decl) span pstate))) (t (b* ((pstate (if token (unread-token pstate) pstate)) ((erp stmt span pstate) (parse-statement pstate))) (retok (block-item-stmt stmt) span pstate)))))))
Function:
(defun parse-block-item-list (pstate) (declare (xargs :guard (parstatep pstate))) (let ((__function__ 'parse-block-item-list)) (declare (ignorable __function__)) (b* (((reterr) nil (irr-span) (irr-parstate)) (psize (parsize pstate)) ((erp item span pstate) (parse-block-item pstate)) ((unless (mbt (<= (parsize pstate) (1- psize)))) (reterr :impossible)) ((erp token & pstate) (read-token pstate))) (cond ((equal token (token-punctuator "}")) (b* ((pstate (unread-token pstate))) (retok (list item) span pstate))) (t (b* ((pstate (if token (unread-token pstate) pstate)) ((erp items last-span pstate) (parse-block-item-list pstate))) (retok (cons item items) (span-join span last-span) pstate)))))))
Theorem:
(defthm return-type-of-parse-statement.stmt (b* (((mv acl2::?erp ?stmt ?span ?new-pstate) (parse-statement pstate))) (stmtp stmt)) :rule-classes :rewrite)
Theorem:
(defthm return-type-of-parse-statement.span (b* (((mv acl2::?erp ?stmt ?span ?new-pstate) (parse-statement pstate))) (spanp span)) :rule-classes :rewrite)
Theorem:
(defthm return-type-of-parse-statement.new-pstate (b* (((mv acl2::?erp ?stmt ?span ?new-pstate) (parse-statement pstate))) (parstatep new-pstate)) :rule-classes :rewrite)
Theorem:
(defthm return-type-of-parse-block-item.item (b* (((mv acl2::?erp ?item ?span ?new-pstate) (parse-block-item pstate))) (block-itemp item)) :rule-classes :rewrite)
Theorem:
(defthm return-type-of-parse-block-item.span (b* (((mv acl2::?erp ?item ?span ?new-pstate) (parse-block-item pstate))) (spanp span)) :rule-classes :rewrite)
Theorem:
(defthm return-type-of-parse-block-item.new-pstate (b* (((mv acl2::?erp ?item ?span ?new-pstate) (parse-block-item pstate))) (parstatep new-pstate)) :rule-classes :rewrite)
Theorem:
(defthm return-type-of-parse-block-item-list.items (b* (((mv acl2::?erp ?items ?span ?new-pstate) (parse-block-item-list pstate))) (block-item-listp items)) :rule-classes :rewrite)
Theorem:
(defthm return-type-of-parse-block-item-list.span (b* (((mv acl2::?erp ?items ?span ?new-pstate) (parse-block-item-list pstate))) (spanp span)) :rule-classes :rewrite)
Theorem:
(defthm return-type-of-parse-block-item-list.new-pstate (b* (((mv acl2::?erp ?items ?span ?new-pstate) (parse-block-item-list pstate))) (parstatep new-pstate)) :rule-classes :rewrite)
Theorem:
(defthm parsize-of-parse-statement-uncond (b* (((mv acl2::?erp ?stmt ?span ?new-pstate) (parse-statement pstate))) (<= (parsize new-pstate) (parsize pstate))) :rule-classes :linear)
Theorem:
(defthm parsize-of-parse-block-item-uncond (b* (((mv acl2::?erp ?item ?span ?new-pstate) (parse-block-item pstate))) (<= (parsize new-pstate) (parsize pstate))) :rule-classes :linear)
Theorem:
(defthm parsize-of-parse-block-item-list-uncond (b* (((mv acl2::?erp ?items ?span ?new-pstate) (parse-block-item-list pstate))) (<= (parsize new-pstate) (parsize pstate))) :rule-classes :linear)
Theorem:
(defthm parsize-of-parse-statement-cond (b* (((mv acl2::?erp ?stmt ?span ?new-pstate) (parse-statement pstate))) (implies (not erp) (<= (parsize new-pstate) (1- (parsize pstate))))) :rule-classes :linear)
Theorem:
(defthm parsize-of-parse-block-item-cond (b* (((mv acl2::?erp ?item ?span ?new-pstate) (parse-block-item pstate))) (implies (not erp) (<= (parsize new-pstate) (1- (parsize pstate))))) :rule-classes :linear)
Theorem:
(defthm parsize-of-parse-block-item-list-cond (b* (((mv acl2::?erp ?items ?span ?new-pstate) (parse-block-item-list pstate))) (implies (not erp) (<= (parsize new-pstate) (1- (parsize pstate))))) :rule-classes :linear)