Skip to main content
Software Engineering

Return to Answer

added 205 characters in body; added 31 characters in body
Source Link
snorkel
snorkel
  • 1
  • 2

It's a big topic but rather than brush you off with a pompous "go read a book, kid" instead I'll gladly give you pointers to help you wrap your head around it.

  1. Tokenize: Scan the code text and break it into a list of tokens.

Tokenize: Scan the code text and break it into a list of tokens.

This step can be tricky because you can't just split the string on spaces, you have to recognize that if (bar) foo += "a string"; is a list of 8 tokens: WORD, OPEN_PAREN, WORD, CLOSE_PAREN, WORD, ASIGNMENT_ADD, STRING_LITERAL, TERMINATOR. As you can see, simply splitting the source code on spaces won't work, you have to read each character as a sequence, so if you encounter an alphanumeric character you keep readreading characters until you hit a non-alphanum character and that string you just read is a WORD to be further classified later. You can decide for yourself how granular your tokenizer is: whether it swallows "a string" as one token called STRING_LITERAL to be further parsed later, or whether it sees "a string" as OPEN_QUOTE, UNPARSED_TEXT, CLOSE_QUOTE, or whatever, this is just one of the many choices you have to decide for yourself as you're coding it.

  1. Lex: So now you have a list of tokens. On some of your tokens you gave asigned an ambiguous classification like WORD because during the first pass you don't spend too much effort trying to figure out the context of each string of characters. So now read you list of tokens again and reclassify the ambiguous tokens to be more specific based on the keywords in your language. So you have a WORD such as "if", and "if" is in your list of special keywords called symbol IF so you change the symbol type of that token from WORD to IF, and any WORD that is not in your special keywords list, such as WORD foo, is an IDENTIFIER.

  2. Parse: So now you turned if (bar) foo += "a string"; a list of lexed tokens that looks like this: IF OPEN_PAREN IDENTIFER CLOSE_PAREN IDENTIFIER ASIGN_ADD STRING_LITERAL TERMINATOR. The step is recognizing sequences of tokens as statements. This is parsing. You do this using a grammar such as:

Lex: So now you have a list of tokens. You probably tagged some tokens with an ambiguous classification like WORD because during the first pass you don't spend too much effort trying to figure out the context of each string of characters. So now read yout list of source tokens again and reclassify each of the ambiguous tokens with a more specific token type based on the keywords in your language. So you have a WORD such as "if", and "if" is in your list of special keywords called symbol IF so you change the symbol type of that token from WORD to IF, and any WORD that is not in your special keywords list, such as WORD foo, is an IDENTIFIER.

Parse: So now you turned if (bar) foo += "a string"; a list of lexed tokens that looks like this: IF OPEN_PAREN IDENTIFER CLOSE_PAREN IDENTIFIER ASIGN_ADD STRING_LITERAL TERMINATOR. The step is recognizing sequences of tokens as statements. This is parsing. You do this using a grammar such as:

STATEMENT := ASIGN_EXPRESSION | IF_STATEMENT

How do you use this? Starting with the first token, try to match your sequence of tokens with these productions. So first you try to match your token list with STATEMENT, so you read the rule for STATEMENT and it says "a STATEMENT is either a ASIGN_EXPRESSION or an IF_STATEMENT" so you try to match ASIGN_EXPRESSION first, so you look up the grammar rule for ASIGN_EXPRESSION and it says "ASIGN_EXPRESSION is an IDENTIFIER followed by an ASIGN_OP followed by an VALUE, so you lookup the grammar rule for IDENTIFIER and you see there is no grammar ruke for IDENTIFIER so therfor that means IDENTIFIER a "terminal" meaning it doesn't require further parsing to match it so you can try to match it directly with your token directly, so. But your first token type is your source listtoken is an IF, and IF is not the same as a IDENTIFIER so match failed. What now? You go back to the STATEMENT rule and try to match the next term: IF_STATEMENT. You lookup IF_STATEMENT, it starts with IF, lookup IF, IF is a terminal, compare terminal with your first token, IF token matches, awesome keep going, next term is PAREN_EXPRESSION, lookup PAREN_EXPRESSION, it's not a terminal, what's it's first term, PAREN_EXPRESSION starts with OPEN_PAREN, lookup OPEN_PAREN, it's a terminal, match OPEN_PAREN to your next token, it matches, .... and so on.

  1. Compile and/or Execute: For certain productions in your grammar you have created handler functions that if given an AST structure it would compile or execute that chunk of AST.

Compile and/or Execute: For certain productions in your grammar you have created handler functions that if given an AST structure it would compile or execute that chunk of AST.

Steps 1 to 3, and some 4, can be made easier using tools like Flex and Bison. (aka. Lex and Yacc) but writing an interpreter yourself from scratch is probably the most empowering exercise any programmer could achieve. All other programming challenges seem trivial after summit-ting this one.

My advice is start small: a tiny language, with a tiny grammar, and try parsing and executing a few simple statements, then grow from there.

It's a big topic but rather than brush you off with pompous "go read a book, kid" instead I'll gladly give you pointers to help you wrap your head around it.

  1. Tokenize: Scan the code text and break it into a list of tokens.

This step can be tricky because you can't just split the string on spaces, you have to recognize that if (bar) foo += "a string"; is a list of 8 tokens: WORD, OPEN_PAREN, WORD, CLOSE_PAREN, WORD, ASIGNMENT_ADD, STRING_LITERAL, TERMINATOR. As you can see, simply splitting the source code on spaces won't work, you have to read each character as a sequence, so if you encounter an alphanumeric character you keep read characters until you hit a non-alphanum and that string you just read is a WORD to be further classified later. You can decide for yourself how granular your tokenizer is: whether it swallows "a string" as one token called STRING_LITERAL to be further parsed later, or whether it sees "a string" as OPEN_QUOTE, UNPARSED_TEXT, CLOSE_QUOTE, or whatever, this is just one of the many choices you have to decide for yourself as you're coding it.

  1. Lex: So now you have a list of tokens. On some of your tokens you gave asigned an ambiguous classification like WORD because during the first pass you don't spend too much effort trying to figure out the context of each string of characters. So now read you list of tokens again and reclassify the ambiguous tokens to be more specific based on the keywords in your language. So you have a WORD such as "if", and "if" is in your list of special keywords called symbol IF so you change the symbol type of that token from WORD to IF, and any WORD that is not in your special keywords list, such as WORD foo, is an IDENTIFIER.

  2. Parse: So now you turned if (bar) foo += "a string"; a list of lexed tokens that looks like this: IF OPEN_PAREN IDENTIFER CLOSE_PAREN IDENTIFIER ASIGN_ADD STRING_LITERAL TERMINATOR. The step is recognizing sequences of tokens as statements. This is parsing. You do this using a grammar such as:

STATEMENT := ASIGN_EXPRESSION | IF_STATEMENT

How do you use this? Starting with the first token, try to match your sequence of tokens with these productions. So first you try to match your token list with STATEMENT, so you read the rule for STATEMENT and it says "a STATEMENT is either a ASIGN_EXPRESSION or an IF_STATEMENT" so you try to match ASIGN_EXPRESSION first, so you look up the grammar rule for ASIGN_EXPRESSION and it says "ASIGN_EXPRESSION is an IDENTIFIER followed by an ASIGN_OP followed by an VALUE, so you lookup the grammar rule for IDENTIFIER and you see there is no grammar so therfor that means IDENTIFIER a "terminal" meaning you can try to match it with your token directly, so your first token type is your source list is IF, and IF is not the same as a IDENTIFIER so match failed. What now? You go back to the STATEMENT rule and try to match the next term: IF_STATEMENT. You lookup IF_STATEMENT, it starts with IF, lookup IF, IF is a terminal, compare terminal with your first token, IF token matches, awesome keep going, next term is PAREN_EXPRESSION, lookup PAREN_EXPRESSION, it's not a terminal, what's it's first term, PAREN_EXPRESSION starts with OPEN_PAREN, lookup OPEN_PAREN, it's a terminal, match OPEN_PAREN to your next token, it matches, .... and so on.

  1. Compile and/or Execute: For certain productions in your grammar you have created handler functions that if given an AST structure it would compile or execute that chunk of AST.

Steps 1 to 3, and some 4, can be made easier using tools like Flex and Bison. (aka. Lex and Yacc) but writing an interpreter yourself from scratch is probably the most empowering exercise any programmer could achieve. All other programming challenges seem trivial after summit-ting this one.

It's a big topic but rather than brush you off with a pompous "go read a book, kid" instead I'll gladly give you pointers to help you wrap your head around it.

Tokenize: Scan the code text and break it into a list of tokens.

This step can be tricky because you can't just split the string on spaces, you have to recognize that if (bar) foo += "a string"; is a list of 8 tokens: WORD, OPEN_PAREN, WORD, CLOSE_PAREN, WORD, ASIGNMENT_ADD, STRING_LITERAL, TERMINATOR. As you can see, simply splitting the source code on spaces won't work, you have to read each character as a sequence, so if you encounter an alphanumeric character you keep reading characters until you hit a non-alphanum character and that string you just read is a WORD to be further classified later. You can decide for yourself how granular your tokenizer is: whether it swallows "a string" as one token called STRING_LITERAL to be further parsed later, or whether it sees "a string" as OPEN_QUOTE, UNPARSED_TEXT, CLOSE_QUOTE, or whatever, this is just one of the many choices you have to decide for yourself as you're coding it.

Lex: So now you have a list of tokens. You probably tagged some tokens with an ambiguous classification like WORD because during the first pass you don't spend too much effort trying to figure out the context of each string of characters. So now read yout list of source tokens again and reclassify each of the ambiguous tokens with a more specific token type based on the keywords in your language. So you have a WORD such as "if", and "if" is in your list of special keywords called symbol IF so you change the symbol type of that token from WORD to IF, and any WORD that is not in your special keywords list, such as WORD foo, is an IDENTIFIER.

Parse: So now you turned if (bar) foo += "a string"; a list of lexed tokens that looks like this: IF OPEN_PAREN IDENTIFER CLOSE_PAREN IDENTIFIER ASIGN_ADD STRING_LITERAL TERMINATOR. The step is recognizing sequences of tokens as statements. This is parsing. You do this using a grammar such as:

STATEMENT := ASIGN_EXPRESSION | IF_STATEMENT

How do you use this? Starting with the first token, try to match your sequence of tokens with these productions. So first you try to match your token list with STATEMENT, so you read the rule for STATEMENT and it says "a STATEMENT is either a ASIGN_EXPRESSION or an IF_STATEMENT" so you try to match ASIGN_EXPRESSION first, so you look up the grammar rule for ASIGN_EXPRESSION and it says "ASIGN_EXPRESSION is an IDENTIFIER followed by an ASIGN_OP followed by an VALUE, so you lookup the grammar rule for IDENTIFIER and you see there is no grammar ruke for IDENTIFIER so that means IDENTIFIER a "terminal" meaning it doesn't require further parsing to match it so you can try to match it directly with your token. But your first source token is an IF, and IF is not the same as a IDENTIFIER so match failed. What now? You go back to the STATEMENT rule and try to match the next term: IF_STATEMENT. You lookup IF_STATEMENT, it starts with IF, lookup IF, IF is a terminal, compare terminal with your first token, IF token matches, awesome keep going, next term is PAREN_EXPRESSION, lookup PAREN_EXPRESSION, it's not a terminal, what's it's first term, PAREN_EXPRESSION starts with OPEN_PAREN, lookup OPEN_PAREN, it's a terminal, match OPEN_PAREN to your next token, it matches, .... and so on.

Compile and/or Execute: For certain productions in your grammar you have created handler functions that if given an AST structure it would compile or execute that chunk of AST.

Steps 1 to 3, and some 4, can be made easier using tools like Flex and Bison. (aka. Lex and Yacc) but writing an interpreter yourself from scratch is probably the most empowering exercise any programmer could achieve. All other programming challenges seem trivial after summit-ting this one.

My advice is start small: a tiny language, with a tiny grammar, and try parsing and executing a few simple statements, then grow from there.

Source Link
snorkel
snorkel
  • 1
  • 2

It's a big topic but rather than brush you off with pompous "go read a book, kid" instead I'll gladly give you pointers to help you wrap your head around it.

Most compilers and/or interpreters work like this:

  1. Tokenize: Scan the code text and break it into a list of tokens.

This step can be tricky because you can't just split the string on spaces, you have to recognize that if (bar) foo += "a string"; is a list of 8 tokens: WORD, OPEN_PAREN, WORD, CLOSE_PAREN, WORD, ASIGNMENT_ADD, STRING_LITERAL, TERMINATOR. As you can see, simply splitting the source code on spaces won't work, you have to read each character as a sequence, so if you encounter an alphanumeric character you keep read characters until you hit a non-alphanum and that string you just read is a WORD to be further classified later. You can decide for yourself how granular your tokenizer is: whether it swallows "a string" as one token called STRING_LITERAL to be further parsed later, or whether it sees "a string" as OPEN_QUOTE, UNPARSED_TEXT, CLOSE_QUOTE, or whatever, this is just one of the many choices you have to decide for yourself as you're coding it.

  1. Lex: So now you have a list of tokens. On some of your tokens you gave asigned an ambiguous classification like WORD because during the first pass you don't spend too much effort trying to figure out the context of each string of characters. So now read you list of tokens again and reclassify the ambiguous tokens to be more specific based on the keywords in your language. So you have a WORD such as "if", and "if" is in your list of special keywords called symbol IF so you change the symbol type of that token from WORD to IF, and any WORD that is not in your special keywords list, such as WORD foo, is an IDENTIFIER.

  2. Parse: So now you turned if (bar) foo += "a string"; a list of lexed tokens that looks like this: IF OPEN_PAREN IDENTIFER CLOSE_PAREN IDENTIFIER ASIGN_ADD STRING_LITERAL TERMINATOR. The step is recognizing sequences of tokens as statements. This is parsing. You do this using a grammar such as:

STATEMENT := ASIGN_EXPRESSION | IF_STATEMENT

IF_STATEMENT := IF, PAREN_EXPRESSION, STATEMENT

ASIGN_EXPRESSION := IDENTIFIER, ASIGN_OP, VALUE

PAREN_EXPRESSSION := OPEN_PAREN, VALUE, CLOSE_PAREN

VALUE := IDENTIFIER | STRING_LITERAL | PAREN_EXPRESSION

ASIGN_OP := EQUAL | ASIGN_ADD | ASIGN_SUBTRACT | ASIGN_MULT

The productions that use "|" between terms means "match any of these", if it there are commas between terms it means "match this sequence of terms"

How do you use this? Starting with the first token, try to match your sequence of tokens with these productions. So first you try to match your token list with STATEMENT, so you read the rule for STATEMENT and it says "a STATEMENT is either a ASIGN_EXPRESSION or an IF_STATEMENT" so you try to match ASIGN_EXPRESSION first, so you look up the grammar rule for ASIGN_EXPRESSION and it says "ASIGN_EXPRESSION is an IDENTIFIER followed by an ASIGN_OP followed by an VALUE, so you lookup the grammar rule for IDENTIFIER and you see there is no grammar so therfor that means IDENTIFIER a "terminal" meaning you can try to match it with your token directly, so your first token type is your source list is IF, and IF is not the same as a IDENTIFIER so match failed. What now? You go back to the STATEMENT rule and try to match the next term: IF_STATEMENT. You lookup IF_STATEMENT, it starts with IF, lookup IF, IF is a terminal, compare terminal with your first token, IF token matches, awesome keep going, next term is PAREN_EXPRESSION, lookup PAREN_EXPRESSION, it's not a terminal, what's it's first term, PAREN_EXPRESSION starts with OPEN_PAREN, lookup OPEN_PAREN, it's a terminal, match OPEN_PAREN to your next token, it matches, .... and so on.

The easiest way to approach this step is you have a function called parse() which you pass it the source code token you're trying to match and the grammar term you're trying to match it with. If the grammar term is not a terminal then you recurse: you call parse() again passing it the same source token and the first term of this grammar rule. This is why it's a called a "recursive descent parser" The parse() function returns (or modifies) your current position in reading the source tokens, it essentially passes back the last token in the matched sequence, and you continue the next call to parse() from there.

Each time parse() matches a production like ASIGN_EXPRESSION you create a structure representing that piece of code. This structure contains references to the original source tokens. You start building a list of these structures. We'll call this entire structure the Abstract Syntax Tree (AST)

  1. Compile and/or Execute: For certain productions in your grammar you have created handler functions that if given an AST structure it would compile or execute that chunk of AST.

So let's look at the piece of your AST that has type ASIGN_ADD. So as an interpreter you have a ASIGN_ADD_execute() function. This function is passed as piece of the AST that corresponds to the parse tree for foo += "a string", so this function looks at that structure and it knows that first term in the structure must be an IDENTIFIER, and the second term is the VALUE, so ASIGN_ADD_execute() passes the VALUE term to a VALUE_eval() function which returns an object representing the evaluated value in memory, then ASIGN_ADD_execute() does a lookup of "foo" in your variables table, and stores a reference to whatever was returned by the eval_value() function.

That's an interpreter. A compiler would instead have handler functions translate the AST into byte code or machine code instead of executing it.

Steps 1 to 3, and some 4, can be made easier using tools like Flex and Bison. (aka. Lex and Yacc) but writing an interpreter yourself from scratch is probably the most empowering exercise any programmer could achieve. All other programming challenges seem trivial after summit-ting this one.

Read these, and good luck!

http://www.iro.umontreal.ca/~felipe/IFT2030-Automne2002/Complements/tinyc.c

http://en.wikipedia.org/wiki/Recursive_descent_parser

Post Made Community Wiki by snorkel