HackerReposA FIELD GUIDE TO OPEN SOURCE
ProSponsor the shelf♧ 0
← Back to top all-time
kragen
peg-bootstrap
JavaScript2008–2025
kragen / peg-bootstrap

peg-bootstrap

A PEG that compiles itself.

Explore on GitHubRead Hacker News discussions
3Distinct people
18Mentions
1Explicit recommenders
76GitHub stars
REPOSITORY AT A GLANCE

What to know before exploring

What it is

A PEG that compiles itself.

GitHub

Where it is used

No documented product use has been verified yet.

What people are saying

Unfortunately this is not yet a compiler; it's a lexer and a parser. Traditionally these are the first things you present in a compilers course, but from my point of view,…

kragen used a recommendation phrase. One indexed comment matches. This is a phrase match, not a verdict.

No classified warning is attached to this page. Read the discussions before treating silence as approval.

Also in these discussions

Mentioned in the same Hacker News threads. That is not proof they are substitutes.

This week on Hacker News

Nov 8–Nov 15 UTC · Direct repository links and separately labeled related project stories. Indexed through 11/15/2026, 1:03:20 AM UTC.

No direct repository links were found in the indexed HN discussions over the past seven days. Older discussions are available below.

Mentions over time

HN mentions by year18 dated mentions

Observed mentions: 2008-12-21 05:53:57 UTC to 2025-07-10 02:37:58 UTC.

012342008-01-01 00:00:00 UTC to 2009-01-01 00:00:00 UTC (exclusive): 1 mentions; 0 submissions, 1 comments20082009-01-01 00:00:00 UTC to 2010-01-01 00:00:00 UTC (exclusive): 2 mentions; 0 submissions, 2 comments2010-01-01 00:00:00 UTC to 2011-01-01 00:00:00 UTC (exclusive): 1 mentions; 0 submissions, 1 comments2011-01-01 00:00:00 UTC to 2012-01-01 00:00:00 UTC (exclusive): 4 mentions; 0 submissions, 4 comments2012-01-01 00:00:00 UTC to 2013-01-01 00:00:00 UTC (exclusive): 0 mentions; 0 submissions, 0 comments2013-01-01 00:00:00 UTC to 2014-01-01 00:00:00 UTC (exclusive): 0 mentions; 0 submissions, 0 comments2014-01-01 00:00:00 UTC to 2015-01-01 00:00:00 UTC (exclusive): 0 mentions; 0 submissions, 0 comments2015-01-01 00:00:00 UTC to 2016-01-01 00:00:00 UTC (exclusive): 0 mentions; 0 submissions, 0 comments2016-01-01 00:00:00 UTC to 2017-01-01 00:00:00 UTC (exclusive): 0 mentions; 0 submissions, 0 comments20162017-01-01 00:00:00 UTC to 2018-01-01 00:00:00 UTC (exclusive): 0 mentions; 0 submissions, 0 comments2018-01-01 00:00:00 UTC to 2019-01-01 00:00:00 UTC (exclusive): 0 mentions; 0 submissions, 0 comments2019-01-01 00:00:00 UTC to 2020-01-01 00:00:00 UTC (exclusive): 0 mentions; 0 submissions, 0 comments2020-01-01 00:00:00 UTC to 2021-01-01 00:00:00 UTC (exclusive): 1 mentions; 0 submissions, 1 comments2021-01-01 00:00:00 UTC to 2022-01-01 00:00:00 UTC (exclusive): 2 mentions; 0 submissions, 2 comments2022-01-01 00:00:00 UTC to 2023-01-01 00:00:00 UTC (exclusive): 3 mentions; 0 submissions, 3 comments2023-01-01 00:00:00 UTC to 2024-01-01 00:00:00 UTC (exclusive): 3 mentions; 2 submissions, 1 comments2024-01-01 00:00:00 UTC to 2025-01-01 00:00:00 UTC (exclusive): 0 mentions; 0 submissions, 0 comments2025-01-01 00:00:00 UTC to 2026-01-01 00:00:00 UTC (exclusive): 1 mentions; 0 submissions, 1 comments2025

Counts come from the repository’s dated source evidence. Index cutoff: 2026-11-02 08:16:59 UTC.

View mention counts and date ranges
UTC ranges include their start and exclude their end. Select a period to filter the source evidence.
PeriodStart (UTC)End (exclusive, UTC)MentionsSubmissionsComments
20082008-01-01 00:00:00 UTC2009-01-01 00:00:00 UTC101
20092009-01-01 00:00:00 UTC2010-01-01 00:00:00 UTC202
20102010-01-01 00:00:00 UTC2011-01-01 00:00:00 UTC101
20112011-01-01 00:00:00 UTC2012-01-01 00:00:00 UTC404
20122012-01-01 00:00:00 UTC2013-01-01 00:00:00 UTC000
20132013-01-01 00:00:00 UTC2014-01-01 00:00:00 UTC000
20142014-01-01 00:00:00 UTC2015-01-01 00:00:00 UTC000
20152015-01-01 00:00:00 UTC2016-01-01 00:00:00 UTC000
20162016-01-01 00:00:00 UTC2017-01-01 00:00:00 UTC000
20172017-01-01 00:00:00 UTC2018-01-01 00:00:00 UTC000
20182018-01-01 00:00:00 UTC2019-01-01 00:00:00 UTC000
20192019-01-01 00:00:00 UTC2020-01-01 00:00:00 UTC000
20202020-01-01 00:00:00 UTC2021-01-01 00:00:00 UTC101
20212021-01-01 00:00:00 UTC2022-01-01 00:00:00 UTC202
20222022-01-01 00:00:00 UTC2023-01-01 00:00:00 UTC303
20232023-01-01 00:00:00 UTC2024-01-01 00:00:00 UTC321
20242024-01-01 00:00:00 UTC2025-01-01 00:00:00 UTC000
20252025-01-01 00:00:00 UTC2026-01-01 00:00:00 UTC101

What Hacker News says

4 sources
kragen·Aug 23, 2011
Like hugi-compo? The latest competition was in 2009, and the winner generated a random ASCII-art maze with a 122-byte MS-DOS .COM file. http://www.fysnet.net/hugi/compoold.htm A 2006 competition was for Sudoku solvers; the winner was 67 bytes. And of course there's a whole demoscene with 32-byte, 64-byte, 128-byte, 256-byte, etc., categories. My dissection of a 16-byte graphics demo (the smallest!) is at http://www.canonical.org/~kragen/demo/fr-016.html. In April some of us were playing with bootstrapping a development environment in MS-DOS from COPY CON: http://lists.canonical.org/pipermail/kragen-discuss/2011-Apr... http://lists.canonical.org/pipermail/kragen-hacks/2011-April... Dave Long put together a version where the machine code was entirely printable ASCII. Brian Raiter wrote a lovely article a few years back on the smallest po
Read the rest
ssible ELF executable, which turns out to be 45 bytes, which unfortunately has been broken by recent Linuxes: http://www.muppetlabs.com/~breadbox/software/tiny/teensy.htm... Based on Brian's work, I wrote a self-compiling compiler for a tiny dialect of Forth: https://github.com/kragen/stoneknifeforth which is about two pages of code if you remove the comments. I also wrote a PEG compiler-compiler in JavaScript which is one page of code: https://github.com/kragen/peg-bootstrap/blob/master/peg.md --- ultimately I want to make a version that generates StoneKnifeForth code instead of JS, but I haven't gotten around to it. I also designed a minimal CPU architecture: https://github.com/kragen/calculusvaporis but I only have software implementations for it so far, and no interesting code. And I wrote a metacircular interpreter for Bicicleta in half a page of code, which I guess is some kind of "minimal coding example": http://lists.canonical.org/pipermail/kragen-hacks/2007-Febru... https://github.com/kragen/screenfuls is a collection of tiny, readable programs that do interesting things.
In An unusual hardware architecture: APA (Associative Processing Array)
kragen·Mar 16, 2011
PEGs are one class of cleanly composable grammars. OMeta uses that attribute of theirs to great advantage. And PEGs are, formally speaking, parsable in worst-case linear time, although whether that linear time is fast enough to be practical is still unknown, and it also potentially uses large linear space. I hope it's not vulgar to post yet another link to my minimal PEG parser generator in one page of code: https://github.com/kragen/peg-bootstrap/blob/master/peg.md In particular, the example here of embedding SQL in C would be pretty trivial to do as a PEG. PEGs can parse some languages that are not context-free — the example from Bryan Ford's thesis is aₓbₓcₓ, where xᵢ means "i repetitions of x". I think there are also context-free languages they can't parse, but I'm not sure. (Operator precedence parsing is particularly ugly in PEGs,
Read the rest
since by default, they don't support left recursion. The OMeta folks figured out how to cleanly support left recursion in PEGs, but you lose the linear-time guarantee.) One very appealing attribute of PEGs is that you can conveniently extend PEGs to support parameterized productions, which could be crucial in building up a library of general-purpose parsing productions that could reasonably be used to shorten the time to define new languages. k4st claims in http://news.ycombinator.com/item?id=2330672 that Pratt top-down operator-precedence parsers are also cleanly composable. I didn't know that, and it seems like a surprising claim, but I don't really understand Pratt parsers yet. Crock has written an excellent article on Pratt parsers as his Beautiful Code chapter, and his JSLint is written with one. I think this is the same text as his chapter: http://javascript.crockford.com/tdop/tdop.html Earley parsers can parse any context-free sentence in worst-case O(N³) time. Context-free grammars can, of course, be easily composed. Quoting Earley's abstract, "It has a time bound proportional to n³ (where n is the length of the string being parsed) in general; it has an n² bound for unambiguous grammars; and it runs in linear time on a large class of grammars, which seems to include most practical context-free programming language grammars." John Aycock has written an Earley parser generator called SPARK which is included with Python, and is reportedly pretty efficient. He's advocated using it specifically because of the composability concern. http://pages.cpsc.ucalgary.ca/~aycock/spark/ Laurie Tratt just posted this other thing about parsing that's currently on the front page of HN; it's really excellent, and duplicates much of what I've written above: http://tratt.net/laurie/tech_articles/articles/parsing_the_s...
In Parsing ought to be easier
kragen·Mar 13, 2011
I agree that PEGs are more interesting. Formally speaking, you can parse PEGs in worst-case linear time with a packrat parser. Practically speaking, the constant factor on that worst case is still much worse than the usual case (the number of nonterminals in your grammar is a factor of the constant factor.) I've written a one-page PEG compiler-compiler (interspersed with many pages of text explaining it) at https://github.com/kragen/peg-bootstrap/blob/master/peg.md.
In Yacc is not dead

MAKE YOURSELF AT HOME

A few shortcuts

/
Search the collection
?
Open this guide
Esc
Close dialogs and navigation

Your saved repositories and interests stay in this browser.