%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -*- Mode: Tex -*- %%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% pvs-gr.txt -- %% Author : Sam Owre %% Created On : Thu Dec 2 13:45:18 1993 %% Last Modified By: Sam Owre %% Last Modified On: Wed Nov 4 16:14:48 1998 %% Update Count : 93 %% Status : Unknown, Use with caution! %% %% HISTORY %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Grammar PVS Case Sensitive Comment Character Newline '%' Operators % Adding new operators may require modification to the following variables, % and functions: % Var or Fun File % ---------- ---- % *pvs-operators* utils.lisp % '(' ')' '-' '+' '*' '/' ':=' '|->' ';' ',' '=' '/=' '<' '<=' '>' '>=' '{' '}' '[' ']' '.' '&' '<=>' '->' ':' '=>' '[#' '#]' '(#' '#)' '(:' ':)' '|' '^' '/\\' '\\/' '[]' '<>' '~' '==' '++' '**' '//' '^^' '<<' '>>' '::' '#' '@' '@@' '##' '[|' '|]' '|[' ']|' '!' '<<=' '>>=' '`' '\'' '[||]' '||' '|-' '|=' '<|' '|>' Lexical Terminals id, number, string %, literal Precedence Information type-expr '[' initial jux medial left expr 'HAS_TYPE' aggregate, 'IN' aggregate % LET '|' medial left '|-' medial right, '|=' medial right 'IFF' medial right, '<=>' medial right 'IMPLIES' medial right, '=>' medial right, 'WHEN' medial right 'OR' medial right, '\\/' medial right, 'XOR' medial right, 'ORELSE' medial right 'AND' medial right, '&' medial right, '/\\' medial right, '&&' medial right, 'ANDTHEN' medial right 'NOT' initial, '~' initial '=' medial left, '/=' medial left, '==' medial left '<' medial left, '<=' medial left, '>' medial left, '>=' medial left, '<<' medial left, '>>' medial left, '<<=' medial left, '>>=' medial left, '<|' medial left, '|>' medial left 'WITH' medial left 'WHERE' medial left, 'IN' medial left '@' medial left, '#' medial left '@@' medial left, '##' medial left, '||' medial left '+' medial left, '-' medial left, '++' medial left, '~' medial left '*' medial left, '/' medial left, '**' medial left, '//' medial left '-' initial 'O' medial left ':' medial left, '::' medial left, 'HAS_TYPE' medial left '[]' initial, '<>' initial '^' medial left, '^^' medial left '`' medial left jux medial left % application adt-or-theories ::= {adt-or-theory+} ; % SO - require endid so that multiple theories parse adt-or-theory ::= {id [theory-formals] ':' {theory | datatype}} ; theory ::= {'THEORY' [exporting]^e 'BEGIN' [assuming-part]^a [theory-part]^t 'END' id} ; datatype ::= {'DATATYPE' ['WITH' 'SUBTYPES' {id^s ++ ','}] 'BEGIN' [{importing [';']^u} ]^2 [assuming-part]^1 adtcase+ 'END' id} <[datatype(opt^1,opt^2,adtcases(plus),id) |datatypes(subtypes(doubleplus),opt^1,opt^2, adtcases(plus),id)]>; adtcase ::= {constructor ':' idop [':' id]} <[adtcase(constructor,idop) |adtcase-subtype(constructor,idop,id)]>; constructor ::= {idop [{'(' {{{idops ':' type-expr} } ++ ','} ')'} ]} ; theory-formals ::= {'[' {theory-formal ++ ','} ']'} ; theory-formal ::= {[{'(' importing ')'} ] idops ':' theory-formal-decl} ; theory-formal-decl ::= {type-keyword ['FROM' type-expr]} | {type-expr} ; exporting ::= {'EXPORTING' exportings [{ 'WITH' exportingmods}]} ; exportings ::= {'ALL' ['BUT' {expname ++ ','}]} | {expname ++ ','} ; expname ::= {idop [':' {type-expr | 'TYPE' | 'FORMULA' }]} % | {'|' idop '|'} ; exportingmods ::= 'ALL' | 'CLOSURE' | modnames ; assuming-part ::= {'ASSUMING' assumings 'ENDASSUMING'} ; assumings ::= {assuming+} ; assuming ::= {importing [';']} | {judgement [';']} | {conversion [';']} | {idops pdformals* ':' assuming-decl [';']} ; theory-part ::= {theory-elt+} ; theory-elt ::= {importing [';']} | {judgement [';']} | {conversion [';']} | {idops [pdformals+] ':' theory-decl [';']^s} ; importing ::= {'IMPORTING' {modname ++ ','}} ; judgement ::= {'JUDGEMENT' {jdecl++','} {'HAS_TYPE'|'SUBTYPE_OF'} type-expr} <{judgement(jdecls(doubleplus), {has-type()|subtype-of()},type-expr)>; jdecl ::= type-expr-sans-name | number | {name [pdformals+]} <[jnamedecl(name)|jappldecl(name,pdf(plus))]> ; ename ::= {name [':' type-expr]} ; conversion ::= {'CONVERSION' {ename++','}} ; pdformals ::= {'(' adformals ')'} ; adformals ::= {adformal++','} ; adformal ::= typed-id | {'(' typed-ids ')'} ; assuming-decl ::= theory-decl | assumption; theory-decl ::= lib-decl | mod-decl | type-decl | var-decl | const-decl | def-decl | ind-decl | formula-decl | datatype | judgement; lib-decl ::= {'LIBRARY' ['='] string} ; mod-decl ::= {'THEORY' '=' modname} ; type-decl ::= {type-keyword [type-def ['CONTAINING' expr]^c]} <[uninterp-type-decl(type-keyword) |type-decl(type-keyword,type-def, [nocontains()|expr]^c)]>; type-keyword ::= 'TYPE' | 'NONEMPTY_TYPE' | 'TYPE+' ; % '=' must appear in name type-def, to avoid overlap with '=' as an opsym. type-def ::= {{'=' | 'FROM' } type-expr} ; var-decl ::= {'VAR' type-expr} ; const-decl ::= {type-expr [const-value]} <[uninterp-const-decl(type-expr) |const-decl(type-expr,const-value)]>; const-value ::= {'=' expr} ; def-decl ::= {'RECURSIVE' type-expr '=' expr 'MEASURE' expr^b ['BY' expr^r]} ; ind-decl ::= {'INDUCTIVE' type-expr '=' expr} ; assumption ::= {'ASSUMPTION' expr} ; formula-decl ::= {formula-name expr} ; type-expr ::= {name [arguments]} <[type-name(name)|type-appl(name,arguments)]> | type-expr-sans-name ; type-expr-sans-name ::= { '(' expr ')'} | {'{' set-formals ['|' expr] '}'} <[enumtype(set-formals) | subtype(set-formals,expr)]> | comp-type-expr ; % Broken out so that type expressions could appear in actual parameters; % names cause conflicts. comp-type-expr ::= recordtype | {[fun-array]^f '[' {dep-type-expr**','} [{'->' type-expr} ]^r ']'} ; recordtype ::= {'[#' {field-decls ++ ','} '#]'} ; field-decls ::= {ids ':' type-expr} ; fun-array ::= 'FUNCTION' | 'ARRAY' ; dep-type-expr ::= type-expr | {idop ':' type-expr} ; %% Expressions expr ::= number | string | name | {'(:' {expr ** ','} ':)'} | {'[|' {expr ** ','} '|]'} | {'(#' {assignment ++ ','} '#)'} | {'(' {expr ** ','} ')'} | {expr '`' {id | number}} <{fieldappl(expr,id)|projappl(expr,number)}> | {expr jux fun-arguments} | {expr 'O' expr^1} | {expr 'IFF' expr^1} | {expr '<=>' expr^1} (),expr-args(list(expr,expr^1)))> | {expr 'IMPLIES' expr^1} | {expr '=>' expr^1} (),expr-args(list(expr,expr^1)))> | {expr 'WHEN' expr^1} | {expr 'OR' expr^1} | {expr '\\/' expr^1} | {expr 'AND' expr^1} | {expr '/\\' expr^1} | {expr '&' expr^1} | {expr 'XOR' expr^1} | {expr 'ANDTHEN' expr^1} | {expr 'ORELSE' expr^1} | {expr '^' expr^1} | {expr '+' expr^1} | {expr '-' expr^1} | {expr '*' expr^1} | {expr '/' expr^1} | {expr '++' expr^1} | {expr '~' expr^1} | {expr '**' expr^1} | {expr '//' expr^1} | {expr '^^' expr^1} | {expr '|-' expr^1} | {expr '|=' expr^1} | {expr '<|' expr^1} | {expr '|>' expr^1} (),expr-args(list(expr,expr^1)))> | {expr '=' expr^1} | {expr '/=' expr^1} | {expr '==' expr^1} | {expr '<' expr^1} | {expr '<=' expr^1} | {expr '>' expr^1} (),expr-args(list(expr,expr^1)))> | {expr '>=' expr^1} =(),expr-args(list(expr,expr^1)))> | {expr '<<' expr^1} | {expr '>>' expr^1} \>(),expr-args(list(expr,expr^1)))> | {expr '<<=' expr^1} | {expr '>>=' expr^1} \>=(),expr-args(list(expr,expr^1)))> | {expr '#' expr^1} | {expr '@@' expr^1} | {expr '##' expr^1} | {'NOT' expr} | {'~' expr} | {'[]' expr} | {'<>' expr} (),expr)> | {'-' expr} | {expr '::' type-expr} | {'IF' expr^c 'THEN' expr^t {{'ELSIF' expr^ic 'THEN' expr^it} }* 'ELSE' expr^e 'ENDIF'} | {{'LAMBDA' | 'FORALL' | 'EXISTS' } lambda-body} | {id '!' {number | lambda-body}^1} <{skovar(id,number)| name-bind-expr(id,lambda-body)}^1> | set-expr | {'LET' {bind++','} 'IN' expr} | {expr 'WHERE' {bind++','}} | {expr 'WITH' '[' {assignment ++ ','} ']'} | {'CASES' expr 'OF' {selection ++ ','} [{'ELSE' expr^e} ] 'ENDCASES'} | {'COND' {cond-case ++ ','} [{',' 'ELSE' '->' expr^e}] 'ENDCOND'} | table-expr ; set-expr ::= {'{' set-formals '|' expr '}'} ; cond-case ::= {expr^l '->' expr^r} ; lambda-body ::= {lambda-formals ':' expr} ; % What we would really like to say here is % lambda-formals ::= adformal++',' | pdformals+ % but this leads to problems: first, the adformals have optional ':'s, % that can lead to ambiguities, second, the optional parens around the % adformals clash with those around the pdformals. Thus we make our own % formals below. Note that lambda-formals may be separated by a comma or % not; an extra check is needed in parse.lisp to ensure it is being used % correctly. lambda-formals ::= {lambda-formal [[',']^c lambda-formals]} <[lambda-formal| lambda-formals(lambda-formal, [nocomma()|comma()]^c, lambda-formals)]>; lambda-formal ::= idop | pdformals ; set-formals ::= {set-formal [[',']^c set-formals]} <[set-formal| set-formals(set-formal,[nocomma()|comma()]^c,set-formals)]>; %set-formals ::= {set-formal [set-formals-rest]} % ; % %set-formals-rest ::= {',' set-formal++','} % % | {set-formal+} % % ; set-formal ::= {{idop [':' type-expr]} | pdformals} <{set-id(idop,[notype()|type-expr])|pdformals}>; selection ::= {idop [{'(' idops ')'} ] ':' expr} ; % assignment ::= {expr {':='|'|->'} !+ @> expr^1 @^ !- } % ; assignment ::= {assign-arg+ {':='|'|->'} expr} ; assign-arg ::= {'(' expr++',' ')'} | {'`' {id | number}} <{field-assign(id)|proj-assign(number)}> | {id ['!' number]} <[assign-id(id)|assign-skoname(id,number)]> | number ; table-expr ::= {'TABLE' [expr^1]^r [',' expr^2]^c [col-heading]^h table-entries 'ENDTABLE'} ; col-heading ::= {'|[' expr^1 {'|' {expr | 'ELSE'}}+ ']|'} ; table-entries ::= {table-entry+} ; table-entry ::= {{'|' [{expr | 'ELSE'}]}+ '||'} ; bind ::= {{simplebind | {'(' simplebind++',' ')'}} '=' expr} ; simplebind ::= {idop pdformals* [':' type-expr]} ; modnames ::= {modname ++ ','} ; modname ::= {[{id^1 '@'}]^p id [actuals] [mappings]^m} ; mappings ::= {'{' mapdecl++ ',' '}'} ; mapdecl ::= {idops [pdformals+ |theory-formals] ':' {type-decl|const-decl} [';' ]^s} ; names ::= {name ++ ','} ; fun-arguments ::= {'(' {expr ** ','} ')'} ; arguments ::= {'(' {expr ++ ','} ')'} ; idops ::= {idop ++ ','} ; idop ::= id | opsym ; ids ::= {id ++ ','} ; typed-id ::= {idop [':' type-expr]^t ['|' expr]^e} ; typed-ids ::= {idops [':' type-expr]^t ['|' expr]^e} <{typed-ids(idops,[no-type-expr()|type-expr]^t, [no-pred()|expr]^e)>; name ::= {[{id '@'}]^L idop [actuals] [{'.' idop^1}]^1} ; unique-name ::= {name [':' {type-expr|formula-name}]} ; opsym ::= '+' <`+()> | '-' <`-()> | '*' <`*()> | '/' <`\/()> | '=' <`=()> | '/=' <`\/=()> | '==' <`==()> | '<' <`\<()> | '<=' <`\<=()> | '>' <`\>()> | '>=' <`\>=()> | 'IFF' | 'IMPLIES' | 'WHEN' | 'OR' | 'AND' | 'NOT' | '&' <`&()> | '/\\' <`\/\\()> | '\\/' <`\\\/()> | '^' <`^()> | '[]' <`\[\]()> | '<>' <`\<\>()> | '~' <`~()> | '=>' <`=\>()> | '<=>' <`\<=\>()> | 'IF' | 'TRUE' | 'FALSE' | 'O' | 'XOR' | 'ORELSE' | 'ANDTHEN' | '++' <`++()> | '**' <`**()> | '//' <`\/\/()> | '^^' <`\^\^()> | '<<' <`\<\<()> | '>>' <`\>\>()> | '<<=' <`\<\<=()> | '>>=' <`\>\>=()> | '#' <`#()> | '@@' <`\@\@()> | '##' <`\#\#()> | '|-' <`\|-()> | '|=' <`\|=()> | '<|' <`\<\|()> | '|>' <`\|\>()> | '[||]' <`\[\|\|\]()> ; actuals ::= {'[' {actual ++ ','} ']'} ; actual ::= expr | comp-type-expr; formula-name ::= 'AXIOM' <`AXIOM()> | 'CHALLENGE' <`CHALLENGE()> | 'CLAIM' <`CLAIM()> | 'CONJECTURE' <`CONJECTURE()> | 'COROLLARY' <`COROLLARY()> | 'FACT' <`FACT()> | 'FORMULA' <`FORMULA()> | 'LAW' <`LAW()> | 'LEMMA' <`LEMMA()> | 'OBLIGATION' <`OBLIGATION()> | 'POSTULATE' <`POSTULATE()> | 'PROPOSITION' <`PROPOSITION()> | 'SUBLEMMA' <`SUBLEMMA()> | 'THEOREM' <`THEOREM()> ;