A guide on using the Zephyr ASDL language (my implementation, specifically) | The Abstract Syntax Description Language

I wrote a short tutorial on using my implementation of ASDL. You can find link to it in the document.

I don’t have a blog or things like that so I just used a Github Gist.

For some reason I got locked out of my Github account and if it was not for a miracle I would have been locked out forever. I barely use Github anyways. I don’t understand why Tarvolds uses this shit corporate hellhole of a website as the primary platform for his projects, which sadly includes Git.

I made a model in ChatGPT to walk me through libgit2 so I can make my own remote host. I don’t like any of the other bloated Git on Web platforms that are out there. I know about Git Tea, but that damn thing is bloated. I want some thing like this guy has: c9x.me

This is what I mean when I say ‘OWN YOUR DATA’. Don’t trust Github, or any of these corporations, with shit.

I get this is really hypocritical to use Gist, then turn around and call Github a soulless corporation. But sadly, I use it BECAUSE it’s a soulless corporation, not in spite of it.

I don’t have money to buy a server. Yes, I am that poor. That is why I have to trust this PaaS and SaaS assholes.

Anyways fuck Github.

Corbin,

Congratulations on taking a step towards self-hosting and meta-circular compilation. ASDL is a great intermediate meta-language and it can be used to abstract any sort of Builder or Command workflow. This is sometimes called a “narrow waist”; ASDL replaces ad-hoc AST-builder objects with a unified protocol and interface.

For example, I encoded Monte into ASDL while rewriting the compiler in Monte, as part of a self-hosting effort. I also wrote a module which parses ASDL and emits Monte modules, including AST-building tools at runtime. Monte supports E-style quasiliterals, including source-code literals. This let our compiler directly consume ASDL files and emit Monte source code. Going beyond the compiler, this allowed me to encode UI elements and widgets as ASTs and use the Command pattern to write widget-handling objects.

ChubakPDP11,

Thanks a lot my good man. Is this Monte? github.com/monte-language/monte I can’t find the source code?

Can you tell me what you think of the code my implementation emits when you got the time? Is it good, bad, medicore etc?

So when you’re building a language, should you always use a builder for the AST specifications? Becuase I figure, you don’t need that in a language like Haskell or OCaml right?

I currently have 3 projects I ping-pong.

1- Marsh, a POSIX shell in C; 2- Awk2X; a translator of AWK to several languages, like C, Python Rust etc. This one is in Haskell 3- Cephyr; a C compiler in OCaml

For Marsh, I am stuck in the job control section. I just can’t seem to find a flow for redirecting input and output. I think I am striking a balance though. I revised the job control like 10 times, literally 10 times.

But for Awk2X and Cephyr, I am kinda stuck at defining the AST. I learned Haskell just last night and I made this AST. I am not ‘stuck’ really, I will move on from it soon.


<span style="font-weight:bold;color:#a71d5d;">data </span><span style="color:#0086b3;">UnaryOp
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#0086b3;">Prefix PrefixOp
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">Postfix PostfixOp
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">deriving</span><span style="color:#323232;"> (</span><span style="color:#0086b3;">Show</span><span style="color:#323232;">)
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">data </span><span style="color:#0086b3;">PrefixOp
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#0086b3;">PrefixIncr
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">PrefixDecr
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">Plus
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">Minus
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">Not
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">deriving</span><span style="color:#323232;"> (</span><span style="color:#0086b3;">Show</span><span style="color:#323232;">)
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">data </span><span style="color:#0086b3;">PostfixOp
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#0086b3;">PostfixIncr
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">PostfixDecr
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">deriving</span><span style="color:#323232;"> (</span><span style="color:#0086b3;">Show</span><span style="color:#323232;">)
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">data </span><span style="color:#0086b3;">BinaryOp
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#0086b3;">Add
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">Sub
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">Mul
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">Div
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">Mod
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">Eq
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">Ne
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">Gt
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">Ge
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">Le
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">Lt
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">And
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">Or
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">deriving</span><span style="color:#323232;"> (</span><span style="color:#0086b3;">Show</span><span style="color:#323232;">)
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">data </span><span style="color:#0086b3;">Lvalue
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#0086b3;">Unfixed String
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">Fixed String String
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">deriving</span><span style="color:#323232;"> (</span><span style="color:#0086b3;">Show</span><span style="color:#323232;">)
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">data </span><span style="color:#0086b3;">Factor
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#0086b3;">Constant Constant
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">Lvalue Lvalue
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">deriving</span><span style="color:#323232;"> (</span><span style="color:#0086b3;">Show</span><span style="color:#323232;">)
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">data </span><span style="color:#0086b3;">Constant
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#0086b3;">String String
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">Integer Int
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">Float Float
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">Regex String
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">deriving</span><span style="color:#323232;"> (</span><span style="color:#0086b3;">Show</span><span style="color:#323232;">)
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">data </span><span style="color:#0086b3;">Expr
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#0086b3;">Unary UnaryOp Factor
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">Binary Factor BinaryOp Factor
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">Ternary Expr Expr Expr
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">StrCat</span><span style="color:#323232;"> [</span><span style="color:#0086b3;">Expr</span><span style="color:#323232;">]
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">Delete Expr
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">Call String</span><span style="color:#323232;"> [</span><span style="color:#0086b3;">Expr</span><span style="color:#323232;">]
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">Assign Lvalue Expr
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">deriving</span><span style="color:#323232;"> (</span><span style="color:#0086b3;">Show</span><span style="color:#323232;">)
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">data </span><span style="color:#0086b3;">Stmt
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#0086b3;">Express Expr
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">For Expr Expr Expr Stmt
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">ForIn Lvalue Lvalue Stmt
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">DoWhile Stmt Expr
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">While Expr Stmt
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">If Expr Stmt</span><span style="color:#323232;"> (</span><span style="color:#0086b3;">Expr</span><span style="color:#323232;">, </span><span style="color:#0086b3;">Stmt</span><span style="color:#323232;">))
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">Return</span><span style="color:#323232;"> (</span><span style="color:#0086b3;">Maybe Expr</span><span style="color:#323232;">)
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">Break
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">Continue
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">Compound</span><span style="color:#323232;"> [</span><span style="color:#0086b3;">Stmt</span><span style="color:#323232;">]
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">deriving</span><span style="color:#323232;"> (</span><span style="color:#0086b3;">Show</span><span style="color:#323232;">)
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">data </span><span style="color:#0086b3;">Pattern
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#0086b3;">Begin
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">End
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">Expr Expr
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">ExprPair Expr Expr
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">data </span><span style="color:#0086b3;">PatternAction
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#0086b3;">WithPattern Pattern</span><span style="color:#323232;"> [</span><span style="color:#0086b3;">Stmt</span><span style="color:#323232;">]
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">JustAction</span><span style="color:#323232;"> [</span><span style="color:#0086b3;">Stmt</span><span style="color:#323232;">]
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">data </span><span style="color:#0086b3;">FunctionDefn </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#0086b3;">FunctionDefn
</span><span style="color:#323232;">  { name </span><span style="font-weight:bold;color:#a71d5d;">:: </span><span style="color:#0086b3;">String</span><span style="color:#323232;">,
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#795da3;">params </span><span style="font-weight:bold;color:#a71d5d;">::</span><span style="color:#323232;"> [</span><span style="font-weight:bold;color:#a71d5d;">String</span><span style="color:#323232;">],
</span><span style="color:#323232;">    body :: [</span><span style="font-weight:bold;color:#a71d5d;">Stmt</span><span style="color:#323232;">]
</span><span style="color:#323232;">  }
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">data </span><span style="color:#0086b3;">Element
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#0086b3;">PattAct PatternAction
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#0086b3;">FnDef FunctionDefn
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">newtype </span><span style="color:#0086b3;">Program </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#0086b3;">Program</span><span style="color:#323232;"> </span><span style="color:#0086b3;">Element
</span>

Now for Cephyr, this one is a bit more complex. Before Cephyr I attempted to make a C compiler several times, and every time I got stuck at the AST.

The problem is, I wanna use OCaml’s modules in the AST. But I don’t know how? I just said fuck it and used top-level types. I am here currently:


<span style="font-weight:bold;color:#a71d5d;">type const_expr
</span><span style="font-weight:bold;color:#a71d5d;">type type_decl
</span><span style="font-weight:bold;color:#a71d5d;">type unary_op
</span><span style="font-weight:bold;color:#a71d5d;">type binary_op
</span><span style="font-weight:bold;color:#a71d5d;">type expr
</span><span style="font-weight:bold;color:#a71d5d;">type stmt
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">type literal </span><span style="color:#323232;">=
</span><span style="color:#323232;">    ConstLiteral </span><span style="font-weight:bold;color:#a71d5d;">of const_lit </span><span style="color:#323232;">| CompoundLiteral </span><span style="font-weight:bold;color:#a71d5d;">of compound_lit
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">and </span><span style="color:#0086b3;">const_lit </span><span style="font-weight:bold;color:#a71d5d;">=
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">IntConst of </span><span style="font-weight:bold;color:#a71d5d;">int *</span><span style="color:#323232;"> int_suffix </span><span style="font-weight:bold;color:#a71d5d;">option
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">FloatCOnst of </span><span style="font-weight:bold;color:#a71d5d;">float *</span><span style="color:#323232;"> float_suffix </span><span style="font-weight:bold;color:#a71d5d;">option
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">CharConst of </span><span style="font-weight:bold;color:#a71d5d;">char *</span><span style="color:#323232;"> charset_prefix </span><span style="font-weight:bold;color:#a71d5d;">option
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">StrConst of </span><span style="font-weight:bold;color:#a71d5d;">string *</span><span style="color:#323232;"> charset_prefix </span><span style="font-weight:bold;color:#a71d5d;">option
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">IdentConst of </span><span style="font-weight:bold;color:#a71d5d;">string *</span><span style="color:#323232;"> const_expr
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">and </span><span style="color:#0086b3;">int_suffix </span><span style="font-weight:bold;color:#a71d5d;">=
</span><span style="color:#323232;">    Long </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">LongLong </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">Unsigned </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">UnsignedLong </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">UnsignedLongLOng
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">and </span><span style="color:#0086b3;">float_suffix </span><span style="font-weight:bold;color:#a71d5d;">=
</span><span style="color:#323232;">    Double </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">LongDouble
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">and </span><span style="color:#0086b3;">charset_prefix </span><span style="font-weight:bold;color:#a71d5d;">=
</span><span style="color:#323232;">    Local </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">U8 </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">U16 </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">U32
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">and </span><span style="color:#0086b3;">compound_lit </span><span style="font-weight:bold;color:#a71d5d;">=
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">ArrayCompound of init_type </span><span style="font-weight:bold;color:#a71d5d;">*</span><span style="color:#323232;"> init_item </span><span style="font-weight:bold;color:#a71d5d;">list
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">StructCompound of init_type </span><span style="font-weight:bold;color:#a71d5d;">*</span><span style="color:#323232;"> init_item </span><span style="font-weight:bold;color:#a71d5d;">list
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">UnionCompound of init_type </span><span style="font-weight:bold;color:#a71d5d;">*</span><span style="color:#323232;"> init_item </span><span style="font-weight:bold;color:#a71d5d;">list
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">and </span><span style="color:#0086b3;">init_item </span><span style="font-weight:bold;color:#a71d5d;">=
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">RegularInit of expr
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">DesignatedInit of designated_init </span><span style="font-weight:bold;color:#a71d5d;">*</span><span style="color:#323232;"> expr
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">and </span><span style="color:#0086b3;">designated_init </span><span style="font-weight:bold;color:#a71d5d;">=
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">ConstExpr of const_expr
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">ConstExprPair of const_expr </span><span style="font-weight:bold;color:#a71d5d;">*</span><span style="color:#323232;"> const_expr
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">Ident of </span><span style="font-weight:bold;color:#a71d5d;">string
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">and </span><span style="color:#0086b3;">init_type </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> type_decl
</span><span style="color:#323232;">
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">type const_expr </span><span style="color:#323232;">=
</span><span style="color:#323232;">  | UnaryConstExpr </span><span style="font-weight:bold;color:#a71d5d;">of </span><span style="color:#323232;">{ factor: </span><span style="font-weight:bold;color:#a71d5d;">literal; </span><span style="color:#323232;">op: </span><span style="font-weight:bold;color:#a71d5d;">unary_op; </span><span style="color:#323232;">}
</span><span style="color:#323232;">  | BinaryConstExpr </span><span style="font-weight:bold;color:#a71d5d;">of </span><span style="color:#323232;">{ left_factor: </span><span style="font-weight:bold;color:#a71d5d;">literal; </span><span style="color:#323232;">right_factor: </span><span style="font-weight:bold;color:#a71d5d;">literal; </span><span style="color:#323232;">op: </span><span style="font-weight:bold;color:#a71d5d;">binary_op; </span><span style="color:#323232;">}
</span><span style="color:#323232;">
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">type primary_factor </span><span style="color:#323232;">=
</span><span style="color:#323232;">    Identifier </span><span style="font-weight:bold;color:#a71d5d;">of string </span><span style="color:#323232;">| NestedExpr </span><span style="font-weight:bold;color:#a71d5d;">of expr </span><span style="color:#323232;">| Literal </span><span style="font-weight:bold;color:#a71d5d;">of literal
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">and </span><span style="color:#0086b3;">expr </span><span style="font-weight:bold;color:#a71d5d;">=
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">Primary of primary_factor
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">Unary of { factor: </span><span style="font-weight:bold;color:#a71d5d;">primary_factor; </span><span style="color:#323232;">op: </span><span style="font-weight:bold;color:#a71d5d;">unary_op; </span><span style="color:#323232;">}
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">Subscript of { factor: </span><span style="font-weight:bold;color:#a71d5d;">primary_factor; </span><span style="color:#323232;">op: </span><span style="font-weight:bold;color:#a71d5d;">subscript_op; </span><span style="color:#323232;">}
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">Binary of { left_factor: </span><span style="font-weight:bold;color:#a71d5d;">expr; </span><span style="color:#323232;">right_factor: </span><span style="font-weight:bold;color:#a71d5d;">expr; </span><span style="color:#323232;">op: </span><span style="font-weight:bold;color:#a71d5d;">binary_op; </span><span style="color:#323232;">}
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">Ternary of { cond: </span><span style="font-weight:bold;color:#a71d5d;">expr; </span><span style="color:#323232;">if_true: </span><span style="font-weight:bold;color:#a71d5d;">expr; </span><span style="color:#323232;">if_false: </span><span style="font-weight:bold;color:#a71d5d;">expr; </span><span style="color:#323232;">}
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">Assignment of { lvalue: </span><span style="font-weight:bold;color:#a71d5d;">expr; </span><span style="color:#323232;">rvalue: </span><span style="font-weight:bold;color:#a71d5d;">expr; </span><span style="color:#323232;">op: </span><span style="font-weight:bold;color:#a71d5d;">assign_op; </span><span style="color:#323232;">}
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">and </span><span style="color:#0086b3;">prefix_unary_op </span><span style="font-weight:bold;color:#a71d5d;">=
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">Negate            
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">LogicalNegate     
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">BitwiseNot        
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">AddressOf         
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">Dereference       
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">PreIncrement      
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">PreDecrement      
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">and </span><span style="color:#0086b3;">postfix_unary_op </span><span style="font-weight:bold;color:#a71d5d;">=
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">PostIncrement     
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">PostDecrement
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">and </span><span style="color:#0086b3;">unary_op </span><span style="font-weight:bold;color:#a71d5d;">=
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">PrefixOp of prefix_unary_op
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">PostfixOp of postfix_unary_op
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">and </span><span style="color:#0086b3;">subscript_op </span><span style="font-weight:bold;color:#a71d5d;">=
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">Index of expr
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">DotMember of expr
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">ArrowMember of expr
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">FunctionCall of expr </span><span style="font-weight:bold;color:#a71d5d;">list
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">and </span><span style="color:#0086b3;">binary_op </span><span style="font-weight:bold;color:#a71d5d;">=
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">Add               
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">Subtract          
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">Multiply          
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">Divide            
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">Modulo            
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">BitwiseAnd        
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">BitwiseOr         
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">BitwiseXor        
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">ShiftLeft         
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">ShiftRight        
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">LogicalAnd        
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">LogicalOr         
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">Equal             
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">NotEqual          
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">LessThan          
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">LessThanOrEqual   
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">GreaterThan       
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">GreaterThanOrEqual 
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">and </span><span style="color:#0086b3;">assign_op </span><span style="font-weight:bold;color:#a71d5d;">=
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">Assignment        
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">AddAssign         
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">SubtractAssign    
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">MultiplyAssign    
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">DivideAssign      
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">ModuloAssign      
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">AndAssign         
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">OrAssign          
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">XorAssign         
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">ShiftLeftAssign   
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">ShiftRightAssign
</span>

It’s still incomplete. I just found out I can use .mli files.

I think Cephyr is the 5th reincaation of my OCaml C compiler. I just spend hours at the AST and get tired of it.

I found lcc, by Fraiser et al:

[github.com/drh/lcc

And I have the book too. I like the book but it’s kinda useless for me because I wanna do SSA. These kinda tree-rewriting mumbo jumbo is too 80s for my taste.

So any help is appreciated. Thanks.

Corbin,

Your code looked alright. Working in C is a risky chore. You’re early in your journey and I think it’s good to get a taste of many of the traditional techniques before turning towards newer fancier algorithms.

“Haskell and OCaml”, hm? The two concepts you need to internalize are katamorphisms and paramorphisms. You may have heard of “recursion schemes”; these two schemes are the ones available on any tree. Fundamentally, most of a compiler is tree-to-tree transformations (nanopasses), and they are expressible as one of two forms:

  • Katamorphism: The leaves of each node are transformed before the branch (bottom-up)
  • Paramorphism: The leaves are transformed after/during the branch transformation (top-down)

If you look again at my AST builder builder, you’ll see .run() and .walk() methods, implementing the recursion for any katamorphism or paramorphism respectively. In Haskell, these are called Traversable types. This is a pun in Monte, where .run() is also the default method; the syntax makes it easy to perform a katamorphism by passing a tree-traversing object directly to the AST.

Your types are alright, but you’ll want to pass a generic parameter through them, turning them into a valid Functor in Haskell or a generic module in OCaml. This is a basic defense against the “AST Decoration Problem”, AKA the “AST Typing Problem”. As you add features to your compiler, you’ll realize why these are necessary.

ChubakPDP11,

(Sorry if this is a double post) I think what you call ‘decoration’ I call 'augmentation;. After many iterations ,I came up with this AST: pastebin.com/NA1DhZF2

I like it, but I am still skeptical as of comitting to it. I really want to use Functors… But i’m nto sure how. These are new concepts to me!

  • All
  • Subscribed
  • Moderated
  • Favorites
  • •
  • programming@programming.dev
  • ngwrru68w68
  • DreamBathrooms
  • Durango
  • osvaldo12
  • everett
  • magazineikmin
  • Youngstown
  • thenastyranch
  • rosin
  • slotface
  • cisconetworking
  • mdbf
  • kavyap
  • khanakhh
  • JUstTest
  • InstantRegret
  • tacticalgear
  • ethstaker
  • normalnudes
  • tester
  • anitta
  • Leos
  • cubers
  • GTA5RPClips
  • megavids
  • provamag3
  • modclub
  • lostlight
  • All magazines
    •