Open mingodad opened 3 years ago
rossberg
commented
3 years ago Very cute!
Question: I'm a bit confused about all the /*empty*/ productions you inserted everywhere, and which seem to make the grammar incorrect. What are they for?
Also, there appears to be some oversimplification of func_type, which now allows params and results to occur in any order. Similarly with the locals in functions, which can be interleaved with instructions.
mingodad
commented
3 years ago Thank you for pointing this out /*empty*/ this is inserted by the tool I made because in bison grammars any rule that starts with | mean the first option is /*empty*/ and looking throut the grammas now I can see that this is not the case with menhir grammars ?
I'll review the menhir grammar.
mingodad
commented
3 years ago After some work I found easier to replace ::= /*empty*/ | by ::= and then replace ::= | to ::= /*empty*/ |, see the result bellow:
/*
From https://github.com/WebAssembly/exception-handling/blob/master/interpreter/text/parser.mly
*/
name ::= STRING
string_list ::= /* empty */ | string_list STRING
ref_kind ::= FUNC | EXTERN
ref_type ::= FUNCREF | EXTERNREF
value_type ::= NUM_TYPE | ref_type
value_type_list ::= /* empty */ | value_type value_type_list
global_type ::= value_type | LPAR MUT value_type RPAR
def_type ::= LPAR FUNC func_type RPAR
func_type ::= /* empty */ | LPAR RESULT value_type_list RPAR func_type | LPAR PARAM value_type_list RPAR func_type | LPAR PARAM bind_var value_type RPAR func_type
table_type ::= limits ref_type
memory_type ::= limits
limits ::= NAT | NAT NAT
type_use ::= LPAR TYPE var RPAR
num ::= NAT | INT | FLOAT
var ::= NAT | VAR
var_list ::= /* empty */ | var var_list
bind_var_opt ::= /* empty */ | bind_var
bind_var ::= VAR
labeling_opt ::= /* empty */ | bind_var
labeling_end_opt ::= /* empty */ | bind_var
offset_opt ::= /* empty */ | OFFSET_EQ_NAT
align_opt ::= /* empty */ | ALIGN_EQ_NAT
instr ::= plain_instr | select_instr_instr | call_instr_instr | block_instr | expr
plain_instr ::= UNREACHABLE | NOP | DROP | BR var | BR_IF var | BR_TABLE var var_list | RETURN | CALL var | THROW var | RETHROW var | LOCAL_GET var | LOCAL_SET var | LOCAL_TEE var | GLOBAL_GET var | GLOBAL_SET var | TABLE_GET var | TABLE_SET var | TABLE_SIZE var | TABLE_GROW var | TABLE_FILL var | TABLE_COPY var var | TABLE_INIT var var | TABLE_GET | TABLE_SET | TABLE_SIZE | TABLE_GROW | TABLE_FILL | TABLE_COPY | TABLE_INIT var | ELEM_DROP var | LOAD offset_opt align_opt | STORE offset_opt align_opt | MEMORY_SIZE | MEMORY_GROW | MEMORY_FILL | MEMORY_COPY | MEMORY_INIT var | DATA_DROP var | REF_NULL ref_kind | REF_IS_NULL | REF_FUNC var | CONST num | TEST | COMPARE | UNARY | BINARY | CONVERT
select_instr ::= SELECT select_instr_results
select_instr_results ::= /* empty */ | LPAR RESULT value_type_list RPAR select_instr_results
select_instr_instr ::= SELECT select_instr_results_instr
select_instr_results_instr ::= LPAR RESULT value_type_list RPAR select_instr_results_instr | instr
call_instr ::= CALL_INDIRECT var call_instr_type | CALL_INDIRECT call_instr_type
call_instr_type ::= type_use call_instr_params | call_instr_params
call_instr_params ::= LPAR PARAM value_type_list RPAR call_instr_params | call_instr_results
call_instr_results ::= /* empty */ | LPAR RESULT value_type_list RPAR call_instr_results
call_instr_instr ::= CALL_INDIRECT var call_instr_type_instr | CALL_INDIRECT call_instr_type_instr
call_instr_type_instr ::= type_use call_instr_params_instr | call_instr_params_instr
call_instr_params_instr ::= LPAR PARAM value_type_list RPAR call_instr_params_instr | call_instr_results_instr
call_instr_results_instr ::= LPAR RESULT value_type_list RPAR call_instr_results_instr | instr
block_instr ::= BLOCK labeling_opt block END labeling_end_opt | LOOP labeling_opt block END labeling_end_opt | IF labeling_opt block END labeling_end_opt | IF labeling_opt block ELSE labeling_end_opt instr_list END labeling_end_opt | TRY labeling_opt block handler_instr | TRY labeling_opt block DELEGATE var
block ::= type_use block_param_body | block_param_body
block_param_body ::= block_result_body | LPAR PARAM value_type_list RPAR block_param_body
block_result_body ::= instr_list | LPAR RESULT value_type_list RPAR block_result_body
handler_instr ::= catch_list_instr END | catch_list_instr catch_all END | catch_all END | END
catch_list_instr ::= catch catch_list_instr | catch
handler ::= /* empty */ | catch_list | catch_list LPAR catch_all RPAR | LPAR catch_all RPAR | LPAR DELEGATE var RPAR
catch_list ::= catch_list LPAR catch RPAR | LPAR catch RPAR
catch ::= CATCH var instr_list
catch_all ::= CATCH_ALL instr_list
expr ::= LPAR expr1 RPAR
expr1 ::= plain_instr expr_list | SELECT select_expr_results | CALL_INDIRECT var call_expr_type | CALL_INDIRECT call_expr_type | BLOCK labeling_opt block | LOOP labeling_opt block | IF labeling_opt if_block | TRY labeling_opt try_block
select_expr_results ::= LPAR RESULT value_type_list RPAR select_expr_results | expr_list
call_expr_type ::= type_use call_expr_params | call_expr_params
call_expr_params ::= LPAR PARAM value_type_list RPAR call_expr_params | call_expr_results
call_expr_results ::= LPAR RESULT value_type_list RPAR call_expr_results | expr_list
if_block ::= type_use if_block_param_body | if_block_param_body
if_block_param_body ::= if_block_result_body | LPAR PARAM value_type_list RPAR if_block_param_body
if_block_result_body ::= if_ | LPAR RESULT value_type_list RPAR if_block_result_body
if_ ::= expr if_ | LPAR THEN instr_list RPAR LPAR ELSE instr_list RPAR | LPAR THEN instr_list RPAR
try_block ::= type_use try_block_param_body | try_block_param_body
try_block_param_body ::= try_block_result_body | LPAR PARAM value_type_list RPAR try_block_param_body
try_block_result_body ::= try_ | LPAR RESULT value_type_list RPAR try_block_result_body
try_ ::= LPAR DO instr_list RPAR handler
instr_list ::= /* empty */ | select_instr | call_instr | instr instr_list
expr_list ::= /* empty */ | expr expr_list
const_expr ::= instr_list
func ::= LPAR FUNC bind_var_opt func_fields RPAR
func_fields ::= type_use func_fields_body | func_fields_body | inline_import type_use func_fields_import | inline_import func_fields_import | inline_export func_fields
func_fields_import ::= func_fields_import_result | LPAR PARAM value_type_list RPAR func_fields_import | LPAR PARAM bind_var value_type RPAR func_fields_import
func_fields_import_result ::= /* empty */ | LPAR RESULT value_type_list RPAR func_fields_import_result
func_fields_body ::= func_result_body | LPAR PARAM value_type_list RPAR func_fields_body | LPAR PARAM bind_var value_type RPAR func_fields_body
func_result_body ::= func_body | LPAR RESULT value_type_list RPAR func_result_body
func_body ::= instr_list | LPAR LOCAL value_type_list RPAR func_body | LPAR LOCAL bind_var value_type RPAR func_body
table_use ::= LPAR TABLE var RPAR
memory_use ::= LPAR MEMORY var RPAR
offset ::= LPAR OFFSET const_expr RPAR | expr
elem_kind ::= FUNC
elem_expr ::= LPAR ITEM const_expr RPAR | expr
elem_expr_list ::= /* empty */ | elem_expr elem_expr_list
elem_var_list ::= var_list
elem_list ::= elem_kind elem_var_list | ref_type elem_expr_list
elem ::= LPAR ELEM bind_var_opt elem_list RPAR | LPAR ELEM bind_var_opt table_use offset elem_list RPAR | LPAR ELEM bind_var_opt DECLARE elem_list RPAR | LPAR ELEM bind_var_opt offset elem_list RPAR | LPAR ELEM bind_var_opt offset elem_var_list RPAR
table ::= LPAR TABLE bind_var_opt table_fields RPAR
table_fields ::= table_type | inline_import table_type | inline_export table_fields | ref_type LPAR ELEM elem_var_list RPAR | ref_type LPAR ELEM elem_expr elem_expr_list RPAR
data ::= LPAR DATA bind_var_opt string_list RPAR | LPAR DATA bind_var_opt memory_use offset string_list RPAR | LPAR DATA bind_var_opt offset string_list RPAR
memory ::= LPAR MEMORY bind_var_opt memory_fields RPAR
memory_fields ::= memory_type | inline_import memory_type | inline_export memory_fields | LPAR DATA string_list RPAR
event ::= LPAR EVENT bind_var_opt event_fields RPAR
event_fields ::= type_use func_type | func_type | inline_import type_use event_fields_import | inline_import event_fields_import | inline_export event_fields
event_fields_import ::= event_fields_import_result | LPAR PARAM value_type_list RPAR event_fields_import | LPAR PARAM bind_var value_type RPAR event_fields_import
event_fields_import_result ::= /* empty */ | LPAR RESULT value_type_list RPAR event_fields_import_result
global ::= LPAR GLOBAL bind_var_opt global_fields RPAR
global_fields ::= global_type const_expr | inline_import global_type | inline_export global_fields
import_desc ::= LPAR FUNC bind_var_opt type_use RPAR | LPAR FUNC bind_var_opt func_type RPAR | LPAR TABLE bind_var_opt table_type RPAR | LPAR MEMORY bind_var_opt memory_type RPAR | LPAR EVENT bind_var_opt type_use RPAR | LPAR EVENT bind_var_opt func_type RPAR | LPAR GLOBAL bind_var_opt global_type RPAR
import ::= LPAR IMPORT name name import_desc RPAR
inline_import ::= LPAR IMPORT name name RPAR
export_desc ::= LPAR FUNC var RPAR | LPAR TABLE var RPAR | LPAR MEMORY var RPAR | LPAR EVENT var RPAR | LPAR GLOBAL var RPAR
export ::= LPAR EXPORT name export_desc RPAR
inline_export ::= LPAR EXPORT name RPAR
type_ ::= def_type
type_def ::= LPAR TYPE type_ RPAR | LPAR TYPE bind_var type_ RPAR
start ::= LPAR START var RPAR
module_fields ::= /* empty */ | module_fields1
module_fields1 ::= type_def module_fields | global module_fields | table module_fields | memory module_fields | event module_fields | func module_fields | elem module_fields | data module_fields | start module_fields | import module_fields | export module_fields
module_var_opt ::= /* empty */ | VAR
module_ ::= LPAR MODULE module_var_opt module_fields RPAR
inline_module ::= module_fields
inline_module1 ::= module_fields1
script_var_opt ::= /* empty */ | VAR
script_module ::= module_ | LPAR MODULE module_var_opt BIN string_list RPAR | LPAR MODULE module_var_opt QUOTE string_list RPAR
action ::= LPAR INVOKE module_var_opt name const_list RPAR | LPAR GET module_var_opt name RPAR
assertion ::= LPAR ASSERT_MALFORMED script_module STRING RPAR | LPAR ASSERT_INVALID script_module STRING RPAR | LPAR ASSERT_UNLINKABLE script_module STRING RPAR | LPAR ASSERT_TRAP script_module STRING RPAR | LPAR ASSERT_RETURN action result_list RPAR | LPAR ASSERT_TRAP action STRING RPAR | LPAR ASSERT_EXCEPTION action RPAR | LPAR ASSERT_EXHAUSTION action STRING RPAR
cmd ::= action | assertion | script_module | LPAR REGISTER name module_var_opt RPAR | meta
cmd_list ::= /* empty */ | cmd cmd_list
meta ::= LPAR SCRIPT script_var_opt cmd_list RPAR | LPAR INPUT script_var_opt STRING RPAR | LPAR OUTPUT script_var_opt STRING RPAR | LPAR OUTPUT script_var_opt RPAR
const ::= LPAR CONST num RPAR | LPAR REF_NULL ref_kind RPAR | LPAR REF_EXTERN NAT RPAR
const_list ::= /* empty */ | const const_list
result ::= const | LPAR CONST NAN RPAR | LPAR REF_FUNC RPAR | LPAR REF_EXTERN RPAR
result_list ::= /* empty */ | result result_list
script ::= cmd_list EOF | inline_module1 EOF
script1 ::= cmd
module1 ::= module_ EOF | inline_module EOF
// Tokens
LPAR ::= "("
RPAR ::= ")"
EXTERN ::= "extern"
EXTERNREF ::= "externref"
FUNCREF ::= "funcref"
MUT ::= "mut"
REF_NULL ::= "ref.null"
REF_FUNC ::= "ref.func"
REF_EXTERN ::= "ref.extern"
REF_IS_NULL ::= "ref.is_null"
NOP ::= "nop"
UNREACHABLE ::= "unreachable"
DROP ::= "drop"
BLOCK ::= "block"
LOOP ::= "loop"
END ::= "end"
BR ::= "br"
BR_IF ::= "br_if"
BR_TABLE ::= "br_table"
RETURN ::= "return"
IF ::= "if"
THEN ::= "then"
ELSE ::= "else"
SELECT ::= "select"
CALL ::= "call"
CALL_INDIRECT ::= "call_indirect"
LOCAL_GET ::= "local.get"
LOCAL_SET ::= "local.set"
LOCAL_TEE ::= "local.tee"
GLOBAL_GET ::= "global.get"
GLOBAL_SET ::= "global.set"
TABLE_GET ::= "table.get"
TABLE_SET ::= "table.set"
TABLE_SIZE ::= "table.size"
TABLE_GROW ::= "table.grow"
TABLE_FILL ::= "table.fill"
TABLE_COPY ::= "table.copy"
TABLE_INIT ::= "table.init"
ELEM_DROP ::= "elem.drop"
MEMORY_SIZE ::= "memory.size"
MEMORY_GROW ::= "memory.grow"
MEMORY_FILL ::= "memory.fill"
MEMORY_COPY ::= "memory.copy"
MEMORY_INIT ::= "memory.init"
DATA_DROP ::= "data.drop"
TRY ::= "try"
DO ::= "do"
CATCH ::= "catch"
CATCH_ALL ::= "catch_all"
DELEGATE ::= "delegate"
THROW ::= "throw"
RETHROW ::= "rethrow"
TYPE ::= "type"
FUNC ::= "func"
START ::= "start"
PARAM ::= "param"
RESULT ::= "result"
LOCAL ::= "local"
GLOBAL ::= "global"
TABLE ::= "table"
MEMORY ::= "memory"
EVENT ::= "event"
ELEM ::= "elem"
DATA ::= "data"
DECLARE ::= "declare"
OFFSET ::= "offset"
ITEM ::= "item"
IMPORT ::= "import"
EXPORT ::= "export"
MODULE ::= "module"
BIN ::= "binary"
QUOTE ::= "quote"
SCRIPT ::= "script"
REGISTER ::= "register"
INVOKE ::= "invoke"
GET ::= "get"
ASSERT_MALFORMED ::= "assert_malformed"
ASSERT_INVALID ::= "assert_invalid"
ASSERT_UNLINKABLE ::= "assert_unlinkable"
ASSERT_RETURN ::= "assert_return"
ASSERT_TRAP ::= "assert_trap"
ASSERT_EXCEPTION ::= "assert_exception"
ASSERT_EXHAUSTION ::= "assert_exhaustion"
NAN Script.CanonicalNan ::= "nan:canonical"
NAN Script.ArithmeticNan ::= "nan:arithmetic"
INPUT ::= "input"
OUTPUT ::= "output"Question: I'm a bit confused about all the
/*empty*/productions you inserted everywhere, and which seem to make the grammar incorrect. What are they for?Also, there appears to be some oversimplification of func_type, which now allows params and results to occur in any order. Similarly with the locals in functions, which can be interleaved with instructions.
I did some fixes (shown on the previous message) could you have a look at it to see if you've pointed out has been resolved ?
One of the objectives of the railroad diagrams is to help visualize the whole grammar and spot possible logical errors.
I've done a experimental tool to convert bison grammars to a kind of EBNF understood by https://www.bottlecaps.de/rr/ui to generate railroad diagrams see bellow the converted
interpreter/text/parser.mlyand with some hand made changes to allow view it at https://www.bottlecaps.de/rr/ui the order of the rules could be changed to a better view of the railroad diagrams. Copy and paste the EBNF bellow on https://www.bottlecaps.de/rr/ui tab Edit Grammar then switch to the tab View Diagram.