Skip to content

Instantly share code, notes, and snippets.

@tuhuynh27
Last active May 18, 2021
Embed
What would you like to do?
"Mini Compiler"
const operators = ['=', '+', '-', '*', '/', '>', '<', '>=', '<=', '==', '!=']
function isOp(v: string) {
for (let i = 0; i < operators.length; i++) {
if (operators[i] == v) return true
}
return false
}
function isNum(v: any) {
return !isNaN(parseFloat(v)) && isFinite(v)
}
type TokenType = 'NUM' | 'LPAREN' | 'RPAREN' | 'OP' | 'EOL' | 'EOF'
interface Token {
type: TokenType,
value?: string
}
function tokenize(str: string): Token[] {
const tokens: Token[] = []
str = str.trim()
let s = ''
for (let index = 0; index < str.length; index++) {
s += str[index]
const peek = str[index + 1]
if (isNum(s.trim()) && !isNum(peek)) {
tokens.push({
type: 'NUM',
value: s.trim()
})
s = ''
}
if (s.trim() === '(' || s.trim() === ')') {
s.trim() === '(' ?
tokens.push({ type: 'LPAREN' }) :
tokens.push({ type: 'RPAREN' })
s = ''
}
if (isOp(s.trim()) && !isOp(peek)) {
tokens.push({ type: 'OP', value: s.trim() })
s = ''
}
if (s === ';' || s === '\n') {
tokens.push({ type: 'EOL' })
s = ''
}
if (index === (str.length - 1)) {
tokens.push({ type: 'EOF' })
s = ''
}
}
return tokens
}
interface ASTNode {
evaluate: () => number | boolean
}
type Operator = 'ADD' | 'SUB' | 'MUL' | 'DIV' |
'LESS_THAN' | 'GREATER_THAN' | 'LESS_EQUAL'| 'GREATER_EQUAL' | 'EQUAL_EQUAL' | 'BANG_EQUAL'
function useBinary(left: ASTNode, operator: Operator, right: ASTNode): ASTNode {
function evaluate(): number | boolean {
switch (operator) {
case 'ADD':
// @ts-ignore
return left.evaluate() + right.evaluate()
case 'SUB':
// @ts-ignore
return left.evaluate() - right.evaluate()
case 'MUL':
// @ts-ignore
return left.evaluate() * right.evaluate()
case 'DIV':
// @ts-ignore
return left.evaluate() / right.evaluate()
case 'LESS_THAN':
// @ts-ignore
return left.evaluate() < right.evaluate()
case 'GREATER_THAN':
// @ts-ignore
return left.evaluate() > right.evaluate()
case 'LESS_EQUAL':
// @ts-ignore
return left.evaluate() <= right.evaluate()
case 'GREATER_EQUAL':
// @ts-ignore
return left.evaluate() >= right.evaluate()
case 'EQUAL_EQUAL':
// @ts-ignore
return left.evaluate() == right.evaluate()
case 'BANG_EQUAL':
// @ts-ignore
return left.evaluate() != right.evaluate()
}
}
return { evaluate }
}
function useLiteral(value: string): ASTNode {
function evaluate() {
return Number(value)
}
return { evaluate }
}
function useGrouping(expr: ASTNode): ASTNode {
function evaluate() {
return expr.evaluate()
}
return { evaluate }
}
function compile(str: string) {
let index = 0
const tokens = tokenize(str)
function current() {
return tokens[index]
}
function add() {
const left = sub()
if (current().value === '+') {
index++
return useBinary(left, 'ADD', sub())
}
return left
}
function sub() {
const left = mul()
if (current().value === '-') {
index++
return useBinary(left, 'SUB', mul())
}
return left
}
function mul(): ASTNode {
const left = all()
if (current().value === '*') {
index++
return useBinary(left, 'MUL', all())
}
return left
}
function all(): ASTNode {
const left = primary()
switch (current().value) {
case '>=':
index++
return useBinary(left, 'GREATER_EQUAL', add())
case '<=':
index++
return useBinary(left, 'LESS_EQUAL', add())
case '==':
index++
return useBinary(left, 'EQUAL_EQUAL', add())
case '>':
index++
return useBinary(left, 'GREATER_EQUAL', add())
case '<':
index++
return useBinary(left, 'LESS_THAN', add())
case '!=':
index++
return useBinary(left, 'BANG_EQUAL', add())
default:
break
}
return left
}
function primary(): ASTNode {
const curr = current()
index++
if (curr.type === 'NUM')
return useLiteral(curr.value)
if (curr.type === 'LPAREN') {
const expr = add()
index++
return useGrouping(expr)
}
}
function parse() {
const asts: ASTNode[] = []
while (current().type !== 'EOF') {
const ast = add()
if (ast) {
asts.push(ast)
}
}
for (const ast of asts) {
console.log(ast.evaluate())
}
}
parse()
}
const str = `
(1+2)+3;
4+(5-2);
`
compile(str)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment