patrickfrey / mewa Goto Github PK

View Code? Open in Web Editor NEW

22.0 4.0 2.0 4.4 MB

Compiler-compiler for writing compiler frontends with Lua

Home Page: https://github.com/patrickfrey/mewa

License: MIT License

Makefile 0.80% C++ 88.27% Shell 1.21% Smarty 0.29% Lua 2.41% Perl 0.62% HTML 0.62% G-code 0.06% xBase 0.01% C 5.72%

compiler-frontend lua cpp17 cpp parser-generator llvm-ir compiler-design compiler-construction compilers compiler

mewa's Introduction

Imagine

... to define the typesystem of your language like this:

Pseudocode Class Declaration

class Obj
{
	function run( param : int ) -> int;
}

Typedb Commands Illustration (Simplified)

intType = typedb:def_type( 0, "int" )

function call( func) return function( this, arg ) ... end end
function init( obj) return function( address) ... end end

object = typedb:def_type( 0, "Obj" )
mt = typedb:def_type( object, "run" )
run = typedb:def_type( mt, "()", call( "Obj_run"), {intType} )
typedb:def_reduction( intType, run, init( intType) )

Mewa

Mewa is a compiler-compiler for prototyping of compiler front-ends for statically-typed programming languages in Lua. You write an attributed grammar in a custom language, a sort of Bison/Yacc-style BNF. The parser creates an AST (Abstract Syntax Tree) with a fixed schema. Lua function calls attached as attributes are called on the AST tree traversal triggered by the compiler after the syntax analysis. A Lua module written in C++ (see typedb API) provides assistance to define the type system of your programming language in a declarative way.

Design Philosophy and Limitations

Mewa is not a framework. It is not instrumented with configuration or plug-ins. The program logic is entirely implemented by the compiler front-end author in Lua. In other words: You write the compiler front-end with Lua using Mewa and not with Mewa using Lua as binding language.
Mewa is not optimized for collaborative work.
Mewa provides no support for the evaluation of different paths of code generation. It leaves all analytical optimization steps to the backend.
Mewa is file-in, file-out, and not suited for implementing Jit compilation.
Mewa does not aim to offer you the greatest variety of possibilities. There exist feature-richer compiler-compilers. Mewa aims to bring projects considered endless for a single person within reach.

LLVM IR

The examples provided here use the intermediate representation (IR) of LLVM for code generation. For reading more see the collected links.

Status

I consider the software as ready for use in projects.

Portability

Build

Currently, there is only GNU Makefile support. CMake support is not planned for this project because the project is too small to justify it and it has not many dependencies. I would rather like to have Makefiles for platforms where GNU Makefile support is not available (e.g. Windows).

Target platforms

Issues around target platforms are discussed here.

Documentation

Mailing List

mewa at freelists

Chat

hash mewa-dev (registered channel) at libera chat

Website

mewa.cc

Contact (E-Mail)

mail at mewa cc

mewa's People

Contributors

Stargazers

Watchers

Forkers

mwilbur gmh5225

mewa's Issues

Sometimes no conflicts reported in grammar

In some cases, conflicts in the language grammar are silently ignored.
I suspect that it has to do with the prioritization of productions that causes the selection of one path over the other.
Probably the prioritization of rules is wrong and an operator precedence implementation like in Bison/Yacc should be implemented.

Duplicate rules in grammar do not lead to a REDUCE/REDUCE conflict

... probably due to states merged together to one. But the thing has to be investigated.
And it is a bug anyway. Duplicates should be reported.

Grammar railroad diagram

Would be nice if mewa could output an EBNF compatible with https://www.bottlecaps.de/rr/ui to generate railroad diagrams (https://en.wikipedia.org/wiki/Syntax_diagram) like was done here https://github.com/mingodad/lalr-parser-test for bison/byacc/lemon.

Meanwhile I did a crud search and replace with Lua string patterns and a bit of manuall fixes to get the EBNF shown bellow for the examples/language1/grammar.g.

Copy and paste the EBNF shown bellow on https://www.bottlecaps.de/rr/ui in the tab "Edit Grammar" then switch to the tab "View Diagram".

/*
BOOLEAN : '';
IDENT	: '[a-zA-Z_]+[a-zA-Z_0-9]*';
DQSTRING: '["]["]' 1;
SQSTRING: "['][']" 1;
UINTEGER: '[0123456789]+';
FLOAT	: '[0123456789]*[.][0123456789]+';
FLOAT	: '[0123456789]*[.][0123456789]+[Ee][+-]{0,1}[0123456789]+';
ILLEGAL	: '[0123456789]+[A-Za-z_]';
ILLEGAL	: '[0123456789]*[.][0123456789]+[A-Za-z_]';
ILLEGAL	: '[0123456789]*[.][0123456789]+[Ee][+-]{0,1}[0123456789]+[A-Za-z_]';
*/

program ::= extern_definitionlist free_definitionlist main_procedure

extern_definitionlist ::= extern_definition extern_definitionlist
			| /*empty*/

free_definitionlist ::= free_definition free_definitionlist
			| /*empty*/

namespace_definitionlist ::= namespace_definition namespace_definitionlist
			| /*empty*/

instruct_definitionlist ::= instruct_definition instruct_definitionlist
			| /*empty*/

inclass_definitionlist ::= inclass_definition inclass_definitionlist
			| /*empty*/

ininterf_definitionlist ::= ininterf_definition ininterf_definitionlist
			| /*empty*/

extern_definition ::= "extern" DQSTRING "function" IDENT typespec "" ";"
			| "extern" DQSTRING "procedure" IDENT "" ";"
			| "extern" DQSTRING "function" IDENT typespec "" ";"
			| "extern" DQSTRING "procedure" IDENT "" ";"

extern_paramdecl ::= typespec IDENT
			| typespec

extern_parameters ::= extern_paramdecl "," extern_parameters
			| extern_paramdecl

extern_paramlist ::= extern_parameters
			| /*empty*/

ininterf_definition ::= "function" IDENT typespec "" funcattribute ";"
			| "procedure" IDENT "" funcattribute ";"
			| "operator" operatordecl typespec "" funcattribute ";"
			| "operator" operatordecl "" funcattribute ";"

funcattribute ::= "const" funcattribute
			| "nothrow" funcattribute
			| /*empty*/

instruct_definition ::= typedefinition ";"
			| variabledefinition ";"
			| structdefinition

inclass_definition ::= typedefinition ";"
			| variabledefinition ";"
			| structdefinition
			| classdefinition
			| interfacedefinition
			| functiondefinition
			| operatordefinition
			| constructordefinition

free_definition ::= namespacedefinition
			| typedefinition ";"
			| variabledefinition ";"
			| structdefinition
			| classdefinition
			| interfacedefinition
			| functiondefinition

namespace_definition ::= namespacedefinition
			| typedefinition ";"
			| structdefinition
			| classdefinition
			| interfacedefinition
			| functiondefinition

typename/*/L1*/ ::= IDENT
			| IDENT "::" typename

typehdr/*/L1*/ ::= typename
			| "const" typename
			| "any" "class" "^"
			| "any" "const" "class" "^"
			| "any" "struct" "^"
			| "any" "const" "struct" "^"

typegen/*/L1*/ ::= typehdr
			| typegen "[" generic_instance "]"
			| typegen "^"
			| typegen "const" "^"

typespec/*/L1*/ ::= typegen
			| typegen "&"

typedefinition ::= "typedef" typegen IDENT
			| "typedef" "function" IDENT typespec ""
			| "typedef" "procedure" IDENT ""
			| "typedef" "function" IDENT typespec "" "nothrow"
			| "typedef" "procedure" IDENT "" "nothrow"

structdefinition ::= "struct" IDENT "{" instruct_definitionlist "}"
			| "generic" "struct" IDENT "[" generic_header "]"
				"{" instruct_definitionlist "}"

interfacedefinition ::= "interface" IDENT "{" ininterf_definitionlist "}"

inheritlist ::= typegen "," inheritlist
			| typegen

namespacedefinition ::= "namespace" IDENT  "{" namespace_definitionlist "}"

classdefinition ::= "class" IDENT "{" inclass_definitionlist "}"
			| "class" IDENT ":" inheritlist "{" inclass_definitionlist "}"
			| "generic" "class" IDENT "[" generic_header "]"
				"{" inclass_definitionlist "}"
			| "generic" "class" IDENT "[" generic_header "]"
				":" inheritlist "{" inclass_definitionlist "}"

linkage ::= "private"
			| "public"
			| /*empty*/

functiondefinition ::= linkage "function" IDENT typespec callablebody
			| linkage "procedure" IDENT callablebody
			| "generic" linkage "function" IDENT "[" generic_header "]"
				 typespec callablebody
			| "generic" linkage "procedure" IDENT "[" generic_header "]"
				 callablebody

constructordefinition ::= linkage "constructor" callablebody
			| "destructor" codeblock

operatordefinition ::= linkage "operator" operatordecl typespec callablebody
			| linkage "operator" operatordecl callablebody

operatordecl ::= "->"
			| "="
			| "+"
			| "-"
			| "*"
			| "/"
			| "%"
			| "&&"
			| "||"
			| "&"
			| "|"
			| "<<"
			| ">>"
			| "~"
			| "!"
			| ""
			| "[" "]"
			| "=="
			| "!="
			| ">="
			| "<="
			| ">"
			| "<"

lambda_paramlist ::= lambda_parameters
			| /*empty*/

lambda_parameters ::= IDENT "," lambda_parameters
			| IDENT

lamda_expression ::= "lambda" "" codeblock

generic_instance_defelem ::= typegen
			| UINTEGER
			| lamda_expression

generic_instance_deflist ::= generic_instance_defelem
			| generic_instance_defelem "," generic_instance_deflist

generic_instance ::= generic_instance_deflist

generic_defaultlist ::= IDENT "=" typegen "," generic_defaultlist
			| IDENT "=" typegen

generic_identlist ::= IDENT "," generic_identlist
			| IDENT "," generic_defaultlist
			| IDENT

generic_header ::= generic_identlist
			| generic_defaultlist

callablebody ::= "" funcattribute "{" statementlist "}"

main_procedure ::= "main" codeblock
			| /*empty*/

impl_paramlist ::= impl_parameters
			| /*empty*/

impl_parameters ::= impl_paramdecl "," impl_parameters
			| impl_paramdecl

impl_paramdecl ::= typespec IDENT

codeblock/*/L1*/ ::= "{" statementlist "}"

statementlist/*/L1*/ ::= statement statementlist
			| /*empty*/

elseblock/*/L1*/ ::= "elseif" "" codeblock	elseblock
			| "elseif" "" codeblock
			| "else" codeblock

catchblock ::= "catch" IDENT	codeblock
			| "catch" IDENT	"," IDENT codeblock

tryblock ::= "try" codeblock

statement/*/L1*/ ::= structdefinition
			| classdefinition
			| functiondefinition
			| typedefinition ";"
			| "var" variabledefinition ";"
			| expression ";"
			| "return" expression ";"
			| "return" ";"
			| "throw" expression "," expression ";"
			| "throw" expression  ";"
			| tryblock catchblock
			| "delete" expression ";"
			| "if" "" codeblock elseblock
			| "if" "" codeblock
			| "while" "" codeblock
			| "with" "" codeblock
			| "with" "" ";"
			| codeblock

variabledefinition ::= typespec IDENT
			| typespec IDENT "=" expression

expression/*/L1*/ ::= "{" expressionlist "}"
			| "{" "}"
			| "new" typespec ":" expression
			| "cast" typespec ":" expression

expression/*/L2*/ ::= IDENT
			| BOOLEAN
			| UINTEGER
			| FLOAT
			| "null"
			| DQSTRING
			| SQSTRING
			| lamda_expression
			| ""

expression/*/L3*/ ::= expression  "="  expression
			| expression  "+="  expression
			| expression  "-="  expression
			| expression  "*="  expression
			| expression  "/="  expression
			| expression  "^="  expression
			| expression  "&="  expression
			| expression  "%="  expression
			| expression  "&&="  expression
			| expression  "||="  expression
			| expression  "&="  expression
			| expression  "|="  expression
			| expression  "<<="  expression
			| expression  ">>="  expression

expression/*/L4*/ ::= expression  "||"  expression

expression/*/L5*/ ::= expression  "&&"  expression

expression/*/L6*/ ::= expression  "|"  expression

expression/*/L7*/ ::= expression  "^"  expression
			| expression  "&"  expression

expression/*/L8*/ ::= expression  "=="  expression
			| expression  "!="  expression
			| expression  "<="  expression
			| expression  "<"  expression
			| expression  ">="  expression
			| expression  ">"  expression

expression/*/L9*/ ::= expression  "+"  expression
			| expression  "-"  expression
			| "&"  expression
			| "-"  expression
			| "+"  expression
			| "~"  expression
			| "!"  expression

expression/*/L10*/ ::= expression  "*"  expression
			| expression  "/"  expression
			| expression  "%"  expression

expression/*/L11*/ ::= expression  "<<"  expression
			| expression  ">>"  expression

expression/*/L12*/ ::= iexpression
			| expression "." IDENT
			| "*" expression

expression/*/L13*/ ::= expression  ""
			| expression  ""
			| expression  "[" expressionlist "]"

iexpression/*/L14*/ ::= expression indirection IDENT

indirection/*/L14*/ ::= "->" indirection
			| "->"

expressionlist/*/L0*/ ::= expression "," expressionlist
			| expression

Script that transformed the grammar:

auto txt = readfile(
	"/home/mingo/dev/lua/mewa/examples/language1/grammar.g"
	);

txt = txt.gsub("%%[^\n]+;", "");
txt = txt.gsub("%s*%b()", "");
txt = txt.gsub("ε", "/*empty*/");
txt = txt.gsub("/L%d+", "/*%1*/");
txt = txt.gsub("%s+= ", " ::= ");
txt = txt.gsub("(%s+);\n", "%1\n");
print(txt);

Inconsistency in typedb interface: get_type, get_types

The functions

typedb:get_type
typedb:get_types

are inconsistent with the rest of the interface, where the other typedb:get_* functions always find something in the current or an enclosing scope. get_type and get_types return a type of a type list in the current scope only.
They should be called this_type and this_types instead. get_type and get_types on the other hand should return a type of a list of types in the current or an enclosing scope to make the interface consistent.

Many SHIFT/REDUCE conflicts reported by lemon or yacc on the same grammar

... to be investigated

byacc-nb -v grammar.g.y
byacc-nb: 1366 shift/reduce conflicts.
1366 conflicts
103 terminal symbols
58 non-terminal symbols
161 total symbols
235 rules
484 states
Exit code: 0
bison-nb -v grammar.g.y
grammar.g.y: warning: 1366 shift/reduce conflicts [-Wconflicts-sr]
grammar.g.y: note: rerun with option '-Wcounterexamples' to generate conflict counterexamples
Exit code: 0

lemon-nb -s y.yl
Can't open the template file "/snap/bin/lempar.c".
1366 parsing conflicts.
Parser statistics:
terminal symbols................... 102
non-terminal symbols............... 57
total symbols...................... 159
rules.............................. 232
states............................. 323
conflicts.......................... 1366
conflicts S/R...................... 1366
conflicts R/R...................... 0
action table entries............... 0
lookahead table entries............ 0
total table size (bytes)........... 0

Exit code: 1

Maybe also languages with indentiation having meaning should be considered

The lexer could be defined to emit terminals for indentation raise or lowering if defined.
A new command is needed in the grammar that defines the name of the terminals emitted.

I do not like spaces in languages having a meaning. But it is currently widespread.

Use luaL_ref references instead of custom hashtable for objects stored in C++ data structures of Mewa

Check if
int r = luaL_ref(L, LUA_REGISTRYINDEX);

can be used to store Lua objects (like constructors) in C structures of Mewa instead of storing them in hashtables.
This can be especially useful in the case of set_instance.

Recommend Projects

React

A declarative, efficient, and flexible JavaScript library for building user interfaces.
Vue.js

🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
Typescript

TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
TensorFlow

An Open Source Machine Learning Framework for Everyone
Django

The Web framework for perfectionists with deadlines.
Laravel

A PHP framework for web artisans
D3

Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

javascript

JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
web

Some thing interesting about web. New door for the world.
server

A server is a program made to process requests and deliver data to clients.
Machine learning

Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Visualization

Some thing interesting about visualization, use data art
Game

Some thing interesting about game, make everyone happy.

Recommend Org

Facebook

We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft

Open source projects and samples from Microsoft.
Google

Google ❤️ Open Source for everyone.
Alibaba

Alibaba Open Source for everyone
D3

Data-Driven Documents codes.
Tencent

China tencent open source team.