-5
私は、関数型、テーブル型、データ構造型の命令型プログラミング言語のいくつかの本質的な要素を含めるように、私のコンパイラのソース言語を拡張しようとしています。例えば、コードのこの部分 メイン（整数x）のための （ ループ（0、X）; ）パーサocamlコール関数
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。ソース言語の拡張 1.1.1。レキシコン
この言語には新しいターミナルシンボル（カンマ）が含まれています。
1.2。文法
命令および表現の文法は、各関数の呼び出しのために製造することによって拡張される（命令の場合には、それはまた、プロシージャ・コールと呼ばれます）。
[instruction] ← ...
| [Call]
[expr] ← ...
| [Call]
[call] ← {id} ([arguments])
[arguments] ← ε
| {[expression],} * [expression]
我々はまた、非末端[fun_decl]（[メイン]を一般化）機能の定義について新たを有し、全体のプログラムのための新しい非終端〔PROG〕、いくつかの機能からなります定義。
[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。関数のパラメータについてセマンティクス
は、値によって通路のモードが選択されます。関数は、戻り値の型のTYを持つ
は、そのシンボルテーブルがそんなに特別な結果タイプTYの変数とリターンが含まれています。関数呼び出しの結果は、結果変数に割り当てられた最後の値です。この変数を読み取った結果は指定されていません。関数呼び出しは式の中でなされた場合
、私たちは関数が結果を返すことを期待しています。呼び出しが命令の場合、関数は結果を返すのを待ちます。
プログラムは、1つの機能のいずれかを手動で命名されていることを前提としている関数のセットです。常にmain関数は整数型の単一のパラメータを期待し、結果を返しません。デフォルトでは、関数は相互に再帰的です。プログラムの各関数は、同じプログラムの他の関数を使用できます。入力nでプログラムを実行すると、main（n）関数呼び出しを実行します。 1.2。コンパイラの拡張子
1.2.1。 SourceAst抽象構文抽象構文
は、我々は、関数呼び出し識別子（呼び出される関数の識別子）と式のリスト（実際のパラメータ）からなる
call = string * list expression
を指定する新しいタイプを定義します。このタイプは、2つの新しいコンストラクタFunCallとcallのProcCallの定義で使用され、それぞれ式と命令位置の関数呼び出しを表します。
2つのコンストラクタfuncallのとProcCallはどちらも2つの命令
FunCall of identifier * string * value list
ProcCall of string * value list
により中間表現IrAstに翻訳された最後の二つの引数と呼ばれる関数の識別子と仮パラメータのリストとして持っています。FunCallのケースには、ファンクションから返される結果の仮想宛先レジスタを示す第1引数もあります。
メインタイプは現在プログラムです。これは、各機能識別子をその定義に関連付けるシンボルテーブルです。関数の定義は、型式
type function_info = {
return: typ option;
formals: typ list;
locals: identify_info Symb_Tbl.t;
code: block
}
で与えられます。これは、最初のシーケンスのメインタイプを一般化します。 returnフィールドには、関数によって返される可能な結果の型が含まれ、フィールドは関数のパラメータの型のリストを構成します（このセッションでは、これらの2つの情報を考慮する必要はありません。 TP8より介入しない）。 各機能には独自のシンボルテーブルがあります。変数のために使用されるシンボルテーブルで
、型identifier_kindが充実し、現在の変数の3種類提供しています：
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)
を今、私は型エラーに
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
を持っている私のコード
があります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
あなたは[MCVE]を検討しましたか？ – glennsl
先生に相談することを検討しましたか？ https://www.lri.fr/~blsk/Compilation/Acte-II/A2.html。 – Lhooq
あなたの投稿を破壊しないでください。あなたの編集は以下の回答を無効にします。 – adiga