Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Dear sir, you have built a compiler

rachitnigam.com

Post reply on HN
Print view View original

91–100 of 177 posts

Re: Dear sir, you have built a compiler

#91

Post by YeGoblynQueenne »

emteycz wrote: post #75
YeGoblynQueenne wrote: post #24

Earlier quoted context omitted.

There's Prolog and its Definite Clause Grammars (DCG) formalism. Here's a DCG for a tiny subset of natural English (copied from wikipedia [1]): sentence --> noun_phrase, verb_phrase. noun_phrase --> det, noun. verb_phrase --> verb, noun_phrase. det --> [the]. det --> [a]. noun --> [cat]. noun --> [bat]. verb --> [eats]. The syntax is just like BNF. "-->" is "::=", terms in []'s are terminals and the rest are nontermi…

Awesome! Do you have any recommendations for good articles about Prolog? I really like the idea. I'm particularly interested in solving assignment problems using constraint logic programming.

To be honest I don't know any short articles that do a good job of describing Prolog.

For a practically-minded programmer, I'd recommend this longer tutorial that guides you through the creation of an old-skewl text-based adventure game:

https://amzi.com/AdventureInProlog/apreface.php

As far as I remember, the tutorial should run on most Prologs without (significant?) modification.

For a more in-depth, high-level, more computer-sciency view try Marcus Triska's pages:

https://www.metalevel.at/prolog

Marcus Triska is also the author of several constraint logic programming libraries, for example:

https://www.swi-prolog.org/man/clpfd.html

Then, there's a number of textbooks. The classics are Clockin and Mellish and Bratko:

Programming in Prolog (Fifth Edition):

https://www2.cs.arizona.edu/classes/cs372/spring15/Programmi...

Prolog programing for AI

https://archive.org/details/prologprogrammin0000brat

I personally really enjoyed this book by George Luger:

AI Algorithms, Data Structures and Idioms in Prolog, Lisp and Java

https://www.cs.fsu.edu/~cap5605/Luger_Supplementary_Text.pdf

For the theory behind DCGs, there's Pereira and Shieber:

Prolog and Natural Language Analysis

http://www.mtome.com/Publications/PNLA/prolog-digital.pdf

And for logic programming theory in general, the seminal source is J. W. Lloyd:

Foundations of logic progamming

https://link.springer.com/book/10.1007/978-3-642-83189-8

Unfortunately, I can't recommend any newer texbooks.

Re: Dear sir, you have built a compiler

#92

Post by hobofan »

melony wrote: post #60
hobofan wrote: post #31

I feel like you can apply the same sentiment to many of the "big scary things" in programming. Things that you don't want to build (as far as "common engineering wisdom" is to be believed): - a compiler - a programming language (not sure that there is a difference to compiler as stated in the article) - a database (query engine) - a CMS - a ERP But sometimes you actually _do_ want to build that (even if every alarm b…

Any tutorials on building the last one? (Beyond basic Rails style CRUD) How do you clone SAP in a weekend?

Heavily depends on what specific incarnation of SAP you mean? If you want to have a SAP replacement for your specific use case, Rails CRUD is the only technological component you need. The much more important part to the recipe is knowledge of the domain model.

That's also where SAP's moat lies. Not with it's technological underpinning, but with the all the different industries and their processes which they've transferred into lines of code (and the ability to extend them with further LOC with the help of a "SAP consultant").

Re: Dear sir, you have built a compiler

#93

Post by einpoklum »

I actually find myself needing something which is close to the front-end of a compiler:

I get a file in a C-like language (say it's C for the sake of discussion and to make life easy), and I want to figure out the names of the top-level functions defined in this file. I am willing to assume that there are no "Gotcha" macros used, which would redefine keywords or types, or otherwise mess up the syntax. The caveat is that I don't want to include any files - even though this file has some include directives; and not including them would mean some types are not defined etc.

What would I do in such a case? Should I take the "not a compiler" approach and start matching regex'es?

Re: Dear sir, you have built a compiler

#94

Post by naasking »

cmyr wrote: post #25
TillE wrote: post #18

YAGNI is a good principle here. Whenever I've found myself thinking about reaching for a parser library, I was over-complicating or over-generalizing the problem. Write the code you need to solve the problem you actually have.

I agree completely. Anytime I’m looking at a parser library I just shake my head and close that browser tab. I’m invariably going to want a hand-rolled recursive descent parser two weeks later, so let’s just get on it.

There's a middle ground with parser combinators.

Re: Dear sir, you have built a compiler

#95

Post by duped »

Koshkin wrote: post #26
throwfaangus wrote: post #9

Earlier quoted context omitted.

Just use flex / bison?

Looks like these are grossly underappreciated these days. They are wonderful, easy to use tools.

I think it's because they're less easy to use tools than writing your own lever/parser, which takes about a day and is fully introspective and debuggable. And if you need decent error reporting at the input it's much easier to thread that through.

Plus almost everything language has some kind of PEG or parser combinator library these days.

Re: Dear sir, you have built a compiler

#97

Post by m-hilgendorf »

At my company (JITX) we've fully committed to compiler architectures in our stack, which makes sense since we're developing an embedded DSL for circuit boards.

It's remarkable how many problems are easier when you just accept it's some kind of compiler problem that needs parsing into a tree you can walk with a pass to spit out the required data. For example in audio networks, you can write a buffer allocation and latency compensation solver as a compiler pass over an AST that represents the network topology, collected by walking the network graph objects. It's way easier to write and test than using the same objects as the network itself.

I will say one of the downsides (if not tackled early) is incremental and streaming data through the architecture. It's a lot easier to write a batch parser than interactive one - which can hurt if you need partial compilation in the future.

Re: Dear sir, you have built a compiler

#98

Post by all2 »

einpoklum wrote: post #93

I actually find myself needing something which is close to the front-end of a compiler: I get a file in a C-like language (say it's C for the sake of discussion and to make life easy), and I want to figure out the names of the top-level functions defined in this file. I am willing to assume that there are no "Gotcha" macros used, which would redefine keywords or types, or otherwise mess up the syntax. The caveat is t…

If the syntax for function definitions is relatively fixed, I'd say use regular expressions. Others have mentioned recursive descent parsers, and you'd be implementing the "base case" portion of one of those.

Not including "includes" is easy. Just don't go looking for them.

---

Edit: the fun part will be trying to implement doc-strings. :D

You wind up with a RDP that has a grammar like

    fn_def := documented
        | un_documented

    documented := doc_string def

    un_documented := def

    doc_string := 

    def :=
Note, for the last two, it will be easier to break those up into pieces. If I were writing a RDP for C# method declarations, I'd have something like

    def := ACCESS_SCOPE MUTABILITY RETURN_TYPE FN_NAME L_PAREN PARAMS R_PAREN

    ACCESS_SCOPE := "private" 

    MUTABILITY := static
        | 

    RETURN_TYPE := "bool"                based on C#'s internal types

    FN_NAME := 

    L_PAREN := "("

    R_PAREN := ")"
Something like that. You'll need to test as you implement, though.

Each of the above grammar definitions should correspond 1 to 1 with a function that you implement. If you need/want help with implementation, my email is in my profile. I'd be more than happy to walk you through this (I've done it before :D specifically this use-case, too, where I was trying to auto-document a language that doesn't have any development/documentation tools).

Re: Dear sir, you have built a compiler

#99

Post by eulers_secret »

hobofan wrote: post #84
eulers_secret wrote: post #72

Earlier quoted context omitted.

> …But sometimes you actually _do_ want to build that… That’s not true for everyone. I’ve been a dev for 20 years and have never done any of those, and I have no desire to at all. That is ok! Programming isn’t some kind of progression to run from “n00b hello world” to “1337 compiler hax0r”, it’s a tool to solve problems with. Many of us will never have to solve these problems or have no interest in these problems. So…

I think I might have used the expression "do want" to vaguely here. Same as you, I have very little desire to write any of those systems, and still try to avoid them as much as possible (as those endeavors usually require more time/energy, etc. and come with higher risks). Maybe it's better put as "But sometimes all your product requirements strongly suggest that you have to build X and there isn't really a way to av…

Thanks for the clarification (even for some rando on the internet), that makes a lot more sense... I think I'll implement a rule for myself where I won't comment on HN posts after first waking up anymore. Agreed that could totally happen!

Re: Dear sir, you have built a compiler

#100

Post by agumonkey »

chubot wrote: post #79
mattgreenrocks wrote: post #67

Earlier quoted context omitted.

I'd argue the idea of an "interpreter" is one of the most foundational concepts of CS. It sounds really basic, but the idea of being handed a description, and doing/creating something based on that is everywhere . It is really quite beautiful.

IIRC it's even in the "Design Patterns" book -- the Interpreter pattern. It really does come up a lot.

The GoF book ? .. I didn't remember seeing it but I have to admit I skimmed with very negative eyes :)
Post reply on HN