2

Recently I am thinking about an algorithm constructed by myself. I call it Replacment Compiling. It works as follows:

Define a language as well as its operators' precedence, such as

(1) store <value> as <id>, replace with: var <id> = <value>, precedence: 1
(2) add <num> to <num>, replace with: <num> + <num>, precedence: 2

Accept a line of input, such as store add 1 to 2 as a;

Tokenize it: <kw,store><kw,add><num,1><kw,to><2><kw,as><id,a><EOF>;

Then scan through all the tokens until reach the end-of-file, find the operation with highest precedence, and "pack" the operation:

<kw,store>(<kw,add><num,1><kw,to><2>)<kw,as><id,a><EOF>

Replace the "sub-statement", the expression in parenthesis, with the defined replacement:

<kw,store>(1 + 2)<kw,as><id,a><EOF>

Repeat until no more statements left:

(<kw,store>(1 + 2)<kw,as><id,a>)<EOF>
(var a = (1 + 2))

Then evaluate the code with the built-in function, eval().

eval("var a = (1 + 2)")

Then my question is: would this algorithm work, and what are the limitations? Is this algorithm works better on simple languages?

2 Answers 2

3

This won't work as-is, because there's no way of deciding the precedence of operations and keywords, but you have essentially defined parsing (and thrown in an interpretation step at the end). This looks pretty close to operator-precedence parsing, but I could be wrong in the details of your vision. The real keys to what makes a parsing algorithm are the direction/precedence it reads the code, whether the decisions are made top-down (figure out what kind of statement and apply the rules) or bottom-up (assemble small pieces into larger components until the types of statements are apparent), and whether the grammar is encoded as code or data for a generic parser. (I'm probably overlooking something, but this should give you a starting point to make sense out of further reading.)

More typically, code is generally parsed using an LR technique (LL if it's top-down) that's driven from a state machine with look-ahead and next-step information, but you'll also find the occasional recursive descent. Since they're all doing very similar things (only implemented differently), your rough algorithm could probably be refined to look a lot like any of them.

For most people learning about parsing, recursive-descent is the way to go, since everything is in the code instead of building what amounts to an interpreter for the state machine definition. But most parser generators build an LL or LR compiler.

And I'm obviously over-simplifying the field, since you can see at the bottom of the Wikipedia pages that there's a smattering of related systems that partly revolve around the kind of grammar you have available. But for most languages, those are the big-three algorithms.

2
  • 1
    Actually I am writing a Java code for this algorithm. It accept the following things: an array of user-defined grammars (in this example, "store <value> as <id>" and "add <num> to <num>"), an array of "translations of grammar" ("var <id> = <value>", "<num>+<num>") and an array of precedence (2, 1), so precedence is defined by user. (p.s. I've read the book Compilers but I think it's too complex to construct a simple language by using the method in the book so I'm creating a tool that provide a simpler way to construct a simple language.)
    – atzlt
    Jun 10, 2020 at 10:52
  • @SketchySketch, I figured it was something along those lines. You might find Pratt Parsers particularly interesting for that use case. It's basically recursive-descent with some interesting parts parameterized. And yeah, I've only used YACC once and I wouldn't say it was worth it for what little I needed it for...
    – John C
    Jun 10, 2020 at 13:47
1

What you've defined is a rewriting system: https://en.wikipedia.org/wiki/Rewriting

You can make a compiler like that, but it's hard work and runs slowly, and if you do a really good job of optimizing it then you'll get conventional table-driven parser. It would be better in the end to learn about those first and just start there.

If you really don't want to use a parser generating tool, then the easiest way to write a parser for a simple language by hand is usually recursive descent: https://en.wikipedia.org/wiki/Recursive_descent_parser

1
  • Thanks for your explanation. Though the algorithm doesn't work well, but I think it is always a good beginning. I'll try recursive descent parsing.
    – atzlt
    Jun 10, 2020 at 12:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.