Parser ocaml Anruffunktion

Question

ich versuche, die Quellsprache meines Compiler zu verlängern, um einige wesentliche Elemente der imperativen Programmiersprachen enthalten: Funktionen, Tabellen, Datenstrukturen. für dieses Stück Code, beispielsweise main (integer x) ( Schleife (0, x); )

loop(integer i, integer r) (
    if line(point(i, r), r) then (
     loop(i+1, r); 
    ) else (); 
) 

    integer point(integer i, integer r) (
    var integer j; 
    j := 0; 
    while (i*i + j*j < r*r) (
     j := j+1; 
    ); 
    result := j; 
) 

    boolean line(integer p, integer r) (
    var integer j; 
    result := false; 
    j := 0; 
    while (j < r+1) (
     if j < p then (
     print(46); 
     result := true; 
    ) else (
     print(35); 
    ); 
     print(32); 
     j := j+1; 
    ); 
    print(10); 
) 

1,1. Erweiterung der Ausgangssprache 1.1.1. Lexicon

Die Sprache enthält das neue Terminal-Symbol, (Komma).

1.1.2. Grammatik

Die Grammatiken der Anweisungen und Ausdrücke werden jeweils um eine Erzeugung für den Aufruf einer Funktion erweitert (im Falle einer Anweisung wird sie auch als Prozeduraufruf bezeichnet).

[instruction] ← ... 
       | [Call] 
     [expr] ← ... 
       | [Call] 

     [call] ← {id} ([arguments]) 
    [arguments] ← ε 
       | {[expression],} * [expression] 

Wir haben auch eine neuen, nicht-terminal [fun_decl] für die Definition einer Funktion (die [Main] verallgemeinert) und ein neuer, nicht-terminal [prog] für ein ganzes Programm, von mehreren Funktions bestehend Definitionen.

[fun_decl] ← {[typ]}? {id} ([parameters]) ([var_decls] [instructions]) 

[parameters] ← ε 
     | {[typ] {id},} * [typ] {id} 

    [prog] ← {[fun_decl]} * 

where {e}? means "e or ε", and {e} * means "e repeated 0 or more times". 

1.1.3. Semantik

Für die Parameter der Funktionen wird ein Wertübergangsmodus gewählt.

Wenn eine Funktion einen Rückgabetyp ty hat, enthält ihre Symboltabelle eine spezielle Ergebnisvariable vom Typ ty und so Return. Das Ergebnis eines Funktionsaufrufs ist der letzte Wert, der der Ergebnisvariablen zugewiesen wurde. Das Ergebnis des Lesens dieser Variablen ist nicht angegeben.

Wenn ein Funktionsaufruf in einem Ausdruck ausgeführt wird, erwarten wir, dass die Funktion ein Ergebnis zurückgibt. Wenn der Aufruf eine Anweisung ist, warten wir, bis die Funktion kein Ergebnis zurückgibt.

Ein Programm ist eine Menge von Funktionen, bei denen man davon ausgeht, dass eine der Funktionen manuell benannt wird. Die Hauptfunktion erwartet ausnahmslos einen einzelnen Parameter vom Typ integer und gibt kein Ergebnis zurück. Standardmäßig sind Funktionen gegenseitig rekursiv: Jede Funktion eines Programms kann jede andere Funktion desselben Programms verwenden. Führen Sie das Programm auf dem Eingang n aus, um einen main (n) -Funktionsaufruf auszuführen. 1.2. Compiler Erweiterung

1.2.1. Abstrakte Syntaxen

In SourceAst abstrakten Syntax definieren wir einen neuen Typ einen Funktionsaufruf

call = string * list expression 

bestehend aus einer Kennung (die Kennung der aufgerufenen Funktion) und eine Liste von Ausdrücken (die eigentlichen Parameter) bezeichnen. Dieser Typ wird bei der Definition von zwei neuen Konstruktoren FunCall des Aufrufs und ProcCall des Aufrufs verwendet, die jeweils einen Funktionsaufruf in Ausdruck und Befehlsposition darstellen.

Die beiden Konstrukteure FUNCALL und ProcCall sind in der Zwischendarstellung IrAst durch die beiden Befehle übersetzt

FunCall of identifier * string * value list 
    ProcCall of string * value list 

Beide haben als letzten beiden Argumente die Kennung der aufgerufenen Funktion und die Liste der formalen Parameter.Der FunCall-Fall hat auch ein erstes Argument, das das virtuelle Zielregister des von der Funktion zurückgegebenen Ergebnisses angibt.

Der Haupttyp ist jetzt Programm, das eine Symboltabelle ist, die jede Funktionskennung mit ihrer Definition verknüpft. Die Definition einer Funktion ist gegeben durch den Typ, der den Haupttyp der ersten Sequenz verallgemeinert. Das Rückgabefeld enthält den Typ des möglichen Ergebnisses, das von der Funktion zurückgegeben wird, und die Felder bilden die Liste der Typen der Parameter der Funktion (für diese Sitzung müssen diese beiden Informationen nicht berücksichtigt werden nicht eingreifen als in TP8). Beachten Sie, dass von nun an jede Funktion ihre eigene Symboltabelle hat.

In der Symboltabelle für Variablen verwendet, wird der Typ identifier_kind angereichert und bietet nun drei Arten von Variablen:

Local always refers to local variables, introduced in particular with var. 
Formal (n) generalizes and replaces FormalX and designates the n-th formal parameter of a function (FormalX corresponds to Formal (1). 
Return is the special variable that must be written to indicate what the result of a function is (only in the case of a function with a return type) 

Jetzt meinen Code Ich habe eine Art Fehler

File "SourceParser.mly", line 79, characters 52-69: 
Error: This variant expression is expected to have type SourceAst.instruction 
    The constructor() does not belong to type SourceAst.instruction 

Es gibt

SourceParser.mly

%{ 

open SourceAst 

%} 

%token <int> CONST_INT 
%token PLUS MINUS STAR 
%token <bool> CONST_BOOL 
%token AND OR 
%token EQUAL NEQ LT LE 
%token <string> IDENT 
%token BEGIN END 
%token IF THEN ELSE 
%token WHILE 
%token SEMI 
%token SET 
%token VAR 
%token INT BOOL 
%token PRINT 
%token EOF 
%token VIRGULE 
%token MAIN 

%left AND OR 
%left LE LT EQUAL NEQ 
%left PLUS MINUS 
%left STAR 

%start main 
%type <SourceAst.main> main 

%% 

main: 
| MAIN; BEGIN; INT; x=IDENT; END; 
BEGIN; vds=var_decls; is=instructions; END; EOF { 
let infox = { typ=TypInteger; kind=Formaln } in 
let init = Symb_Tbl.singleton x infox in 
let merge_vars _ v1 v2 = match v1, v2 with 
    | _, Some(v) -> Some v 
    | Some(v), _ -> Some v 
    | _, _  -> None 
in 
let locals = Symb_Tbl.merge merge_vars init vds in 
{locals = locals; code=is} } 
; 

var_decls: 
| (* empty *)      { Symb_Tbl.empty         } 
| vd=var_decl; SEMI; vds=var_decls { let (id, t) = vd in 
       let info = { typ=t; kind=Local } in 
       Symb_Tbl.add id info vds } 
; 

var_decl: 
| VAR; tid=typed_ident { tid } 
; 

typed_ident: 
| t=typ; id=IDENT { (id, t) } 
; 

typ: 
| INT { TypInteger } 
| BOOL { TypBoolean } 
; 

    instructions: 
| (* empty *)        { []  } 
| i=instruction; SEMI; is=instructions  { i :: is } 
; 

instruction: 
| l=location; SET; e=expression      { Set(l, e)  } 
| WHILE; e=expression; b=block      { While(e, b) } 
| IF; e=expression; THEN; b1=block; ELSE; b2=block { If(e, b1, b2) } 
| PRINT; BEGIN; e=expression; END     { Print(e)  } 
| c=call           {    } 
; 

block: 
| BEGIN; is=instructions; END  { is } 
; 

expression: 
| lit=literal        { Literal(lit)  } 
| loc=location       { Location(loc)  } 
| BEGIN; e=expression; END    { e     } 
| e1=expression; op=binop; e2=expression { Binop(op, e1, e2) } 
| c=call         {     }         
; 

literal: 
| i=CONST_INT { Int i } 
| b=CONST_BOOL { Bool b } 
; 

location: 
| id=IDENT { Identifier id } 
; 

call: 
|id=IDENT;BEGIN;a=argument;END {} 
; 

argument: 
|args = separated_list(VIRGULE, expression) { args }  
; 

fun_decl: 
|option(typ);id=IDENT ;BEGIN;p=parameters;END;BEGIN;v=var_decls; i=instructions;END {} 
; 

parameters : 
|param = separated_list (VIRGULE,typed_ident) {param} 
; 

progs: 
|l=list(fun_decl) {l} 
; 

prog: 
|(* empty *) { []  } 
|progs;EOF { } 
; 


%inline binop: 
| PLUS { Add } 
| MINUS { Sub } 
| STAR { Mult } 
| EQUAL { Eq } 
| NEQ { Neq } 
| LT  { Lt } 
| LE  { Le } 
| AND { And } 
| OR  { Or } 
; 

Sourcelexer.mll

{ 

open Lexing 
open SourceParser 

let id_or_keyword = 
let h = Hashtbl.create 17 in 
List.iter (fun (s, k) -> Hashtbl.add h s k) 
    [ "true",  CONST_BOOL(true); 
"false", CONST_BOOL(false); 
"while", WHILE; 
"if",  IF; 
"then",  THEN; 
"else",  ELSE; 
"integer", INT; 
"boolean", BOOL; 
"print", PRINT; 
"main",  MAIN; 
"var",  VAR; 
    ] ; 
fun s -> 
    try Hashtbl.find h s 
    with Not_found -> IDENT(s) 

} 

let digit = ['0'-'9'] 
let alpha = ['a'-'z' 'A'-'Z'] 
let ident = ['a'-'z' '_'] (alpha | '_' | '\'' | digit)* 

rule token = parse 
| ['\n' ' ' '\t' '\r']+ 
    { token lexbuf } 
| "(*" 
    { comment lexbuf; token lexbuf } 
| digit+ 
    { CONST_INT (int_of_string (lexeme lexbuf)) } 
| ident 
    { id_or_keyword (lexeme lexbuf) } 
| "(" 
    { BEGIN } 
| ")" 
    { END } 
| ";" 
    { SEMI } 
| ":=" 
    { SET } 
| "+" 
    { PLUS } 
| "-" 
    { MINUS } 
| "*" 
    { STAR } 
| "==" 
    { EQUAL } 
| "!=" 
    { NEQ } 
| "<" 
    { LT } 
| "<=" 
    { LE } 
| "&&" 
    { AND } 
| "||" 
    { OR } 
| _ 
    { failwith ("Unknown character : "^(lexeme lexbuf)) } 
| eof 
    { EOF } 
| "," 
    {VIRGULE} 

and comment = parse 
| "(*" 
    { comment lexbuf; comment lexbuf } 
| "*)" 
    {() } 
| _ 
    { comment lexbuf } 
| eof 
    { failwith "Unterminated comment" } 

SourceAst.ml

(* Typed abstract syntax *) 

module Symb_Tbl = Map.Make (String) 

(* Main program: a symbol table and a code block *) 
type main = { 
locals: identify_info Symb_Tbl.t; 
code: block; 
} 

(* The symbol table contains, for each variable: 
    - its nature: local variable or formal parameter 
    - its type: integer or boolean 
*) 
and identify_kind = 
| Local (* Local variable *) 
| Formaln (* formal parameter n *) 
| Return 
and identify_info = {typ: typ; kind: identify_kind} 
    and typ = 
| TypInteger 
| TypBoolean 

    (* A code block is a list of instructions *) 
    and block = statement list 
    and instruction = 
    | Set of location * expression (* Assignment *) 
    | While of expression * block (* Loop *) 
    | If of expression * block * block (* Branch *) 
    | Print of expression (* Display *) 
    (* | ProcCall of string * value list *) 

and expression = 
| Literal of literal (* Immediate value *) 
| Location of location (* Value in memory *) 
| Binop of binop * expression * expression (* Binary operation *) 
(* | FunCall to identify * string * value list *) 

and literal = 
| Int of int (* Integer constant *) 
| Bool of bool (* Boolean constant *) 

and location = 
| Identifier of string (* Variable in memory *) 

and binop = 
| Add (* + *) | Mult (* * *) | Sub (* - *) 
| Eq (* == *) | Neq (*! = *) 
| Lt (* <*) | The (* <= *) 
| And (* && *) | Gold (* || *) 

and call = string * expression list 




(for debugging: a display. 
[print_main m] produces a string representing the program 
*) 
open Printf 

let print_typ = function 
| TypInteger -> "integer" 
| TypBoolean -> "boolean" 
let print_identifier_info i = print_typ i.typ 

let print_symb_tbl tbl = 
Symb_Tbl.fold (fun v i s -> 
(sprintf "var% s% s; \ n" (print_identifier_info i) v)^s 
) tbl "" 

let print_literal = function 
| Int i -> sprintf "% d" i 
| Bool b -> if b then "true" else "false" 
let print_location = function 
| Identify x -> x 
let print_binop = function 
| Add -> "+" 
| Mult -> "*" 
| Sub -> "-" 
| Eq -> "==" 
| Neq -> "! =" 
| Lt -> "<" 
| The -> "<=" 
| And -> "&&" 
| Gold -> "||" 
let rec print_expression = function 
| Literal bed -> print_literal bed 
| Location id -> print_location id 
| Binop (op, e1, e2) -> sprintf "(% s% s% s)" (print_expression e1)  (print_binop op) (print_expression e2) 

let offset o = String.make (2 * o) '' 
let rec print_block o = function 
| [] -> "" 
| i :: b -> (offset o)^(print_instruction o i)^"; \ n"^ (print_block o b) 
and print_instruction o = function 
| Set (id, e) -> sprintf "% s: =% s" (print_location id)   (print_expression) 
| While (e, b) -> 
sprintf "while% s (\ n% s% s)" 
    (print_expression e) 
    (print_block (o + 1) b) (offset o) 
| If (e, b1, b2) -> 
sprintf "if% s then (\ n% s% s) else (\ n% s% s)" 
    (print_expression e) 
    (print_block (o + 1) b1) (offset o) 
    (print_block (o + 1) b2) (offset o) 
| Print (e) -> sprintf "print (% s)" (print_expression e) 

let print_main m = 
sprintf "main (int x) (\ n% s% s) \ n" 
(print_symb_tbl m.locals) (print_block 1 m.code) 

IrAst.ml

module Symb_Tbl = GotoAst.Symb_Tbl 

type label   = GotoAst.label 
type literal   = GotoAst.literal 
type identifier_info = GotoAst.identifier_info 
type binop   = GotoAst.binop 

type main = { 
    locals: identifier_info Symb_Tbl.t; 
    code: block; 
    } 

and block = (label * instruction) list 
and instruction = 
| Value of identifier * value     (* Chargement d'une valeur *) 
| Binop of identifier * binop * value * value (* Opération binaire  *) 
| Print of value        (* Affichage    *) 
| Label of label        (* Point de saut    *) 
| Goto  of label        (* Saut     *) 
| CondGoto of value * label      (* Saut conditionnel  *) 
| Comment of string        (* Commentaire    *) 
| FunCall of identifier * string * value list 
| ProcCall of    string * value list 
and identifier = string (* Identifiant d'un registre virtuel *) 

and value = 
| Literal of literal (* Valeur immédiate *) 
| Identifier of identifier (* Registre virtuel *) 




open Printf 

let rec print_block = function 
| []   -> "\n" 
| (l, i) :: b -> sprintf "%s: %s\n%s" l (print_instruction i)  (print_block b) 

and print_instruction = function 
| Value(dest, v) -> sprintf "%s <- %s" dest (print_value v) 
| Binop(dest, op, v1, v2) -> sprintf "%s <- %s %s %s" 
dest (print_value v1) (SourceAst.print_binop op) (print_value v2) 
| Print(v)   -> sprintf "print(%s)" (print_value v) 
| Label(lab)  -> lab 
| Goto(lab)  -> sprintf "goto %s" lab 
| CondGoto(v, lab) -> sprintf "goto %s when %s" lab (print_value v) 
| Comment(c)  -> sprintf "# %s" c 

and print_value = function 
| Literal(lit) -> SourceAst.print_literal lit 
| Identifier(id) -> id 

Answer 1

Eine semantische Aktion in der Regel sollte einen Wert (semantisches Attribut) einen Typs erzeugt das ist für diese Regel entweder mit der type Direktive definiert oder wird vom OCaml Typchecker abgeleitet. In Ihrem Fall haben Sie mehrere Fälle, in denen eine semantische Aktion leer gelassen, zum Beispiel

| c=call           {    } 

Die leere Regel entspricht einen Wert vom Typ unit. Deshalb sehen Sie diese seltsame Fehlermeldung, die besagt, dass der Konstruktor () (also der Datenkonstruktor des Einheitswertes) nicht zum Typ instruction gehört.

wäre mein Vorschlag, alle solche semantischen Stubs mit einem Ausdruck zu ersetzen, die eine Ausnahme auslöst, beispielsweise

| c=call   {failwith "Not implemented" }