parser

8 Articles

Pratt Parsing For Algebraic Expressions

July 3, 2023 by 10 Comments

Parsing algebraic expressions is always a pain. If you need to compute, say, 2+4*2, the answer should be the same as (2 + (4 *2)), not ((2 + 4) * 2) — in other words, the right answer is 10, not 12. The classic way to do this is to use two stacks and a table of precedences for the operators. However, [Martin Janiczek] prefers to use Pratt Parsers and wants to show you how they work.

The parser is named after [Vaughn Pratt]. The algorithm works with a table of precedence where operators with higher precedence have higher numbers. It then builds a left and right portion of a string, using recursion. So if you consider 2+4*2, you wind up, on the first pass, with (2+ parse(4*2)). The second parse returns a full expression to produce: (2+(4*2)).

Continue reading “Pratt Parsing For Algebraic Expressions” →

Create A Compiler Step-By-Step

November 27, 2022 by 19 Comments

While JavaScript might not be the ideal language to write a production compiler, you might enjoy the “Create Your Own Compiler” tutorial that does an annotated walkthrough of “The Super Tiny Compiler” and teaches you the basics of writing a compiler from scratch.

The super tiny compiler itself is about 200 lines of code. The source code is well, over 1,000 but that’s because of the literate programming comments. The fancy title comments are about half as large as the actual compiler.

The compiler’s goal is to take Lisp-style functions and convert them to equivalent C-style function calls. For example: (add 5 (subtract 3 1) would become add(5,subtract(3,1)).

Of course, there are several shortcut methods you could use to do this pretty easily, but the compiler uses a structure like most full-blown modern compilers. There is a parser, an abstract representation phase, and code generation.

Continue reading “Create A Compiler Step-By-Step” →

parser drill

Machining Wood Inlays, No CNC Required

October 17, 2021 by 13 Comments

It’s almost hard to remember a time when the obvious answer to most questions about manufacturing wasn’t “Throw it on the CNC.” CNC machines have become so entrenched that the acronym has become a verb; few people would misunderstand a statement like “Let’s just CNC that.”

But before CNC machines became so ubiquitous, there were plenty of clever tricks for cutting material in a controlled fashion, as [Pask] shows us with this tool to machine wood for inlays. The tool is called a parser (or passer) drill, and is designed for use in conjunction with a steel template. [Pask]’s version seems pretty easy to make; a pair of mild steel bars are forged flat into spade shapes before having a cutting surface ground into them. The two halves of the drill are welded together and ground down to fit in the chuck of a hand drill, a modern nod to the fact that few people will want to use the traditional bow and breastplate that drove the original parser drills.

In use, a steel template that determines the shape of the inlay is affixed to the workpiece. The cutting edges of the bits are plunged into the template cutout to machine out the wood; the overhangs of the bits act as depth stop and guide. It only takes a few seconds to make a neat, CNC-free inlay. The video below shows the tool being made and in action.

It’s nice to see what can be accomplished without the need for fancy CNC machines. Not that we have anything against them, of course, but when the same results can be had with some scraps of steel and a little ingenuity, it’s pretty impressive. Looking for something between manual tools and CNC for woodworking? The pantorouter might be just your speed.

Continue reading “Machining Wood Inlays, No CNC Required” →

Interpreters In Scala

July 16, 2021 by 15 Comments

You might think of interpreters as only good for writing programs. Many people learned programming on some kind of interpreter — like BASIC — because you get immediate feedback and don’t have to deal with the complexities of a compiler. But interpreters can have other uses like parsing configuration files, for example. [Sakib] has a very complete tutorial about writing an interpreter in Scala, but even if you use another language, you might find the tutorial useful.

We were impressed because the tutorial uses formal parsing using a lexer and a parser. This is how you’d be taught to do it in a computer science class, but not how everyone does it.

Continue reading “Interpreters In Scala” →

DIY Regular Expressions

October 29, 2020 by 12 Comments

In the Star Wars universe, not everyone uses a lightsaber, and those who do wield them had to build them themselves. There’s something to be said about that strategy. Building a car or a radio is a great way to learn how those things work. That’s what [Low Level JavaScript] points out about regular expressions. Sure, a lot of people think they are scary. So why not write your own regular expression parser and engine? Get that under your belt and you’ll probably never fear another regular expression.

Of course, most of us probably won’t do it ourselves, but you can still watch the process in the video below. The code is surprisingly short, but don’t expect all the bells and whistles you might find in Python or even Perl.

Continue reading “DIY Regular Expressions” →

Parsing Math In Python

September 18, 2020 by 10 Comments

Programming computers used to be harder. Don’t get us wrong — today, people tend to solve harder problems with computers, but the fundamental act of programming is easier. We have high-level languages, toolkits, and even help from our operating systems. Most people never have to figure out how to directly read from a disk drive, deblock the data into records, and perform multiplication using nothing but shifts and adds. While that’s a good thing, sometimes it is good to study the basics. That was [gnebehay’s] thought when his university studies were too high level, so he decided to write an arithmetic expression parser in Python. It came out in about 100 lines of code.

Interpreting math expressions is one of those things that seems simple until you get into it. The first problem is correctly lexing the input — a term that means splitting into tokens. For a human, it seems simple that 5-3 is three tokens, {5, -, and 3} and that’s easy to figure out. But what about 5+-3? That’s also three tokens: {5,+,-3}. Tricky.

Continue reading “Parsing Math In Python” →

Tiny Programming Language In 25 Lines Of Code

January 22, 2018 by 9 Comments

There are certain kinds of programs that fascinate certain kinds of software hackers. Maybe you are into number crunching, chess programs, operating systems, or artificial intelligence. However, on any significant machine, most of the time those activities will require some sort of language. Sure, we all have some processor we can write hex code for in our head, but you really want at least an assembler if not something sturdier. Writing languages can be addictive, but jumping right into a big system like gcc and trying to make changes is daunting for anyone. If you want a gentle introduction, check out [mgechev’s] language that resides in 25 lines of Javascript.

The GitHub page bills it as a tiny compiler, although that is a bit misleading and even the README says it is a transpiler. Actually, the code reads a simple language, uses recursive descent parsing to build a tree, and then uses a “compiler” to convert the tree to JavaScript (which can then be executed, of course). It can also just interpret the tree and produce a numerical answer.

Continue reading “Tiny Programming Language In 25 Lines Of Code” →