Class: Calcula::Parser

Inherits:
Object
  • Object
show all
Includes:
Exprs
Defined in:
lib/Parser.rb

Overview

The parser for the Calcula language written in Ruby. Please, if adding a grammar rule, document it.

Author:

  • Paul T.

Constant Summary collapse

EQL_LIKE_OPS = 
[:OP_EQ, :OP_NE, :OP_LT, :OP_GT, :OP_LE, :OP_GE]
MUL_LIKE_OPS = 
[:OP_REM, :OP_MUL, :OP_DIV, :PAREN_O]
ADD_OR_SUB = 
[:OP_ADD, :OP_SUB]
STMT_TERMINATOR = 
[:DISP, :ASSERT]

Instance Method Summary collapse

Constructor Details

#initialize(toks) ⇒ Parser

Constructs a new parser with the specified Tokens

Parameters:

  • toks (Array<Calcula::Token>) —

    The tokens most likely generated from the lexer



27
28
29
30
 
# File 'lib/Parser.rb', line 27

def initialize(toks)
  @toks = toks
  @i = 0
end

Instance Method Details

#addLikeExpr ⇒ Calcula::Expr

Parses the syntax rule of addLikeExpr addLikeExpr = mulLikeExpr ((OP_ADD | OP_SUB) mulLikeExpr)*

Returns:



224
225
226
227
228
 
# File 'lib/Parser.rb', line 224

def addLikeExpr
  return consumeWhen(:mulLikeExpr, BinopExpr) do |id, _txt|
    ADD_OR_SUB.index(id) != nil
  end
end

#basicValExpr ⇒ Calcula::Expr

Parses the syntax rule for basicValExpr basicValExpr = numExpr | composeExpr | lambdaExpr

Returns:



325
326
327
328
329
330
331
332
333
334
335
336
337
338
 
# File 'lib/Parser.rb', line 325

def basicValExpr
  tmp = lookahead()
  parseError(nil, "Expected numExpr or identExpr") if tmp == nil

  case tmp.id
  when :NUM then
    return numExpr()
  when :ID then
    return composeExpr()
  when :LAMBDA then
    return lambdaExpr()
  else parseError(tmp, "Expected numExpr or identExpr")
  end
end

#composeExpr ⇒ Object

Parses the syntax rule for composeExpr composeExpr = identExpr (COMPOSE identExpr)*



342
343
344
345
346
 
# File 'lib/Parser.rb', line 342

def composeExpr
  return consumeWhen(:identExpr, BinopExpr) do |id, _txt|
    id == :COMPOSE
  end
end

#consume(tokId) ⇒ Calcula::Token

Performs a lookahead and checks to see if the next token is the one specified. If the specified token is not found, then the method parseError is called.

(see #lookahead) (see #parseError)

Parameters:

  • tokId (Symbol) —

    The type of token being expected

Returns:



51
52
53
54
55
56
57
58
59
60
61
 
# File 'lib/Parser.rb', line 51

def consume(tokId)
  cons = lookahead()
  if cons == nil then
    parseError(nil, "Expected token #{tokId}")
  elsif cons.id == tokId then
    @i += 1
    return cons
  else
    parseError(@toks[@i], "Expected token #{tokId}")
  end
end

#consumeWhen(childrenMethod, exprClass) {|id, text| ... } ⇒ Calcula::Expr

Performs lookahead and constructs a parse tree. This could only be used on parse trees with the grammar of self = $1:child ($2:SOMETHING $3:child)*

The tree being constructed must have the initialization sequence of SubclassOfExpr.new($2, $1, $3)

Parameters:

  • childrenMethod (Symbol) —

    The name of child in the example grammar

  • exprClass (Constant (class name)) —

    The SubclassOfExpr in the example

Yields:

  • (id, text) —

    Predicate for whether or not lookahead should continue

Yield Parameters:

  • id (Symbol) —

    The current lookahead token's id

  • text (String) —

    The current lookahead token's text

Yield Returns:

  • (true, false) —

    true if consumption should continue, false otherwise

Returns:



180
181
182
183
184
185
186
187
188
 
# File 'lib/Parser.rb', line 180

def consumeWhen(childrenMethod, exprClass) # => Take a block (predicate)
  rst = self.send(childrenMethod)
  tmp = lookahead
  while tmp != nil && yield(tmp.id, tmp.text) do
    rst = exprClass.new(consume(tmp.id), rst, self.send(childrenMethod))
    tmp = lookahead
  end
  return rst
end

#defExpr ⇒ Calcula::Expr

Parses the syntax rule of defExpr defExpr = LET identExpr PAREN_O paramsExpr PAREN_C OP_EQ equation | LET identExpr OP_EQ equation

Returns:



111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
 
# File 'lib/Parser.rb', line 111

def defExpr
  consume(:LET)
  name = identExpr()
  val = nil

  maybeParenO = lookahead
  parseError(nil, "Expected a complete function declaration or '='") if maybeParenO == nil

  case maybeParenO.id
  when :PAREN_O then
    consume(:PAREN_O)
    params = paramsExpr()
    consume(:PAREN_C)
    consume(:OP_EQ)
    act = equation()
    val = FuncExpr.new(params, act)
  when :OP_EQ then
    consume(:OP_EQ)
    val = equation()
  else
    parseError(maybeParenO, "Expected complete function declaration or '='")
  end
  AssignExpr.new(name, val)
end

#equalLikeExpr ⇒ Calcula::Expr

Parses the syntax rule of equalLikeExpr equalLikeExpr = addLikeExpr ((OP_EQ | OP_NE | OP_LT | OP_GT | OP_LE | OP_GE) addLikeExpr)?

Returns:



214
215
216
217
218
 
# File 'lib/Parser.rb', line 214

def equalLikeExpr
  return consumeWhen(:addLikeExpr, BinopExpr) do |id, _txt|
    EQL_LIKE_OPS.index(id) != nil
  end
end

#equation ⇒ Calcula::Expr

Parses the syntax rule of expr equation = logicOrExpr

Returns:



103
104
105
 
# File 'lib/Parser.rb', line 103

def equation
  logicOrExpr()
end

#exponentExpr ⇒ Calcula::Expr

Parses the syntax rule for exponentExpr exponentExpr = parenExpr (OP_POW parenExpr)*

Returns:



290
291
292
293
294
 
# File 'lib/Parser.rb', line 290

def exponentExpr
  return consumeWhen(:parenExpr, BinopExpr) do |id, _txt|
    id == :OP_POW
  end
end

#identExpr ⇒ Calcula::Expr

Parses the syntax rule for identExpr identExpr = ID

Returns:



398
399
400
401
 
# File 'lib/Parser.rb', line 398

def identExpr
  tok = consume(:ID)
  return IdentExpr.new(tok)
end

#lambdaExpr ⇒ Calcula::Expr

Parses the syntax rule for lambdaExpr lambdaExpr = LAMBDA paramsExpr equation

Returns:



372
373
374
375
376
 
# File 'lib/Parser.rb', line 372

def lambdaExpr
  consume(:LAMBDA)
  params = paramsExpr()
  return FuncExpr.new(params, equation())
end

#logicAndExpr ⇒ Calcula::Expr

Parses the syntax rule of logicAndExpr logicAndExpr = equalLikeExpr (OR equalLikeExpr)*

Returns:



204
205
206
207
208
 
# File 'lib/Parser.rb', line 204

def logicAndExpr
  return consumeWhen(:equalLikeExpr, BinopExpr) do |id, _txt|
    id == :OR
  end
end

#logicNotExpr ⇒ Calcula::Expr

Parses the syntax rule of logicNotExpr logicNotExpr = NOT logicOrExpr

Returns:



153
154
155
156
157
158
159
160
161
162
163
164
 
# File 'lib/Parser.rb', line 153

def logicNotExpr
  tmp = lookahead
  parseError(nil, "Expected an equation") if tmp == nil
  if tmp.id == :NOT then
    tmp = consume(tmp.id)
  end
  rst = logicOrExpr
  if tmp.id == :NOT then
    rst = UnaryExpr.mkPrefix(tmp, rst)
  end
  return rst
end

#logicOrExpr ⇒ Calcula::Expr

Parses the syntax rule of logicOrExpr logicOrExpr = logicAndExpr (AND logicAndExpr)*

Returns:



194
195
196
197
198
 
# File 'lib/Parser.rb', line 194

def logicOrExpr
  return consumeWhen(:logicAndExpr, BinopExpr) do |id, _txt|
    id == :AND
  end
end

#lookahead ⇒ Calcula::Token?

Finds the next non-ignored token and returns it

Returns:

  • (Calcula::Token, nil) —

    nil if the next non-ignored token nil. This could mean end of script.



66
67
68
69
70
71
72
73
74
75
76
77
 
# File 'lib/Parser.rb', line 66

def lookahead
  return nil if @toks[@i] == nil
  while @toks[@i].id == :WS || @toks[@i].id == :COMMENT do
    @i += 1
    return nil if @toks[@i] == nil
  end
  if @i < @toks.length then
    return @toks[@i]
  else
    return nil
  end
end

#mulLikeExpr ⇒ Calcula::Expr

Parses the syntax rule of mulLikeExpr mulLikeExpr = prefixExpr ((OP_REM | OP_MUL | OP_DIV) mulLikeExpr)? | prefixExpr (PAREN_O equation mulLikeExpr)?

Returns:



235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
 
# File 'lib/Parser.rb', line 235

def mulLikeExpr
  rst = prefixExpr
  tmp = lookahead
  while tmp != nil && MUL_LIKE_OPS.index(tmp.id) != nil do
    if tmp.id == :PAREN_O then
      paren = consume(tmp.id)
      appliedOn = equation
      consume(:PAREN_C)
      rst = BinopExpr.new(paren, rst, appliedOn)
    else
      rst = BinopExpr.new(consume(tmp.id), rst, prefixExpr)
    end
    tmp = lookahead
  end
  return rst
end

#numExpr ⇒ Calcula::Expr

Parses the syntax rule for numExpr numExpr = NUM (RAT NUM)?

Returns:



382
383
384
385
386
387
388
389
390
391
392
 
# File 'lib/Parser.rb', line 382

def numExpr
  tok = consume(:NUM)
  maybeRat = lookahead()
  if maybeRat != nil and maybeRat.id == :RAT then
    consume(:RAT)
    bottom = consume(:NUM)
    return RatExpr.new(tok, bottom)
  else
    return NumExpr.new(tok)
  end
end

#paramsExpr ⇒ Calcula::Expr

Parses the syntax rule for paramsExpr paramsExpr = ID (COMMA ID)+ | ID

Returns:



353
354
355
356
357
358
359
360
361
362
363
364
365
366
 
# File 'lib/Parser.rb', line 353

def paramsExpr
  # NOTE: Do not change this part to using the `consumeWhen` method.
  #       it does not work like that.
  params = [consume(:ID)]
  loop do
    begin
      consume(:COMMA)
    rescue RuntimeError
      break
    end
    params << consume(:ID)
  end
  return ParamsExpr.new(params)
end

#parenExpr ⇒ Calcula::Expr

Parses the syntax rule of parenExpr parenExpr = PAREN_O equation PAREN_C | SQUARE_O equation SQUARE_C | basicValExpr

Returns:



302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
 
# File 'lib/Parser.rb', line 302

def parenExpr
  tmp = lookahead()
  parseError(nil, "Expected PAREN_O or an equation") if tmp == nil

  case tmp.id
  when :PAREN_O then
    head = consume(:PAREN_O)
    inner = equation()
    tail = consume(:PAREN_C)
    return BracedExpr.new(head, tail, inner)
  when :SQUARE_O then
    head = consume(:SQUARE_O)
    inner = equation()
    tail = consume(:SQUARE_C)
    return BracedExpr.new(head, tail, inner)
  else return basicValExpr()
  end
end

#parse ⇒ Calcula::Expr?

Begins to parse the list of tokens and tries to convert it into an expression tree

Returns:

  • (Calcula::Expr, nil) —

    If an expression tree can be constructed, nil otherwise



82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
 
# File 'lib/Parser.rb', line 82

def parse
  tmp = lookahead
  if tmp == nil then
    nil
  else
    case tmp.id
    when :LET then
      defExpr
    when :COMMA then
      consume(:COMMA) # Comma is like semicolons in ruby. Optional!
      parse
    else
      printExpr
    end
  end
end

#parseError(unexpectedTok, msg) ⇒ Object

Raises an error with seemingly useful message

Parameters:

  • unexpectedTok (Calcula::Token, nil) —

    The token that was found instead, nil if End of file was found.

  • msg (String) —

    The additional message or the reason of the error

Raises:

  • (RuntimeError) —

    Calling this method raises this error



37
38
39
40
41
42
 
# File 'lib/Parser.rb', line 37

def parseError(unexpectedTok, msg)
  if unexpectedTok == nil then
    raise "Unexpected EOF: #{msg != '' ? msg : '<no message>'}"
  end
  raise "Unexpected token #{unexpectedTok}: #{msg != '' ? msg : '<no message>'}"
end

#postfixExpr ⇒ Calcula::Expr

Parses the syntax rule for postfixExpr postfixExpr = exponentExpr ROUND_DOLLAR?

Returns:



273
274
275
276
277
278
279
280
281
282
283
284
 
# File 'lib/Parser.rb', line 273

def postfixExpr
  base = exponentExpr
  maybePostfix = lookahead
  if maybePostfix != nil then
    case maybePostfix.id
    when :ROUND_DOLLAR then
      return UnaryExpr.mkPostfix(consume(:ROUND_DOLLAR), base)
    end
    # Default case fallsthough and base itself gets returned
  end
  return base
end

#prefixExpr ⇒ Calcula::Expr

Parses the syntax rule for prefixExpr prefixExpr = (OP_SUB | OP_ADD)? postfixExpr

Returns:



256
257
258
259
260
261
262
263
264
265
266
267
 
# File 'lib/Parser.rb', line 256

def prefixExpr
  tmp = lookahead
  parseError(nil, "Expected a prefix operator or equation") if tmp == nil

  case tmp.id
  when :OP_SUB, :OP_ADD then
    op = consume(tmp.id)
    return UnaryExpr.mkPrefix(op, postfixExpr)
  else
    return postfixExpr
  end
end

#printExpr ⇒ Object

Parses the syntax ruke for printExpr printExpr = equation (DISP | ASSERT)?



139
140
141
142
143
144
145
146
147
 
# File 'lib/Parser.rb', line 139

def printExpr
  base = equation()
  maybeDisp = lookahead()
  if maybeDisp != nil && STMT_TERMINATOR.index(maybeDisp.id) != nil then
    UnaryExpr.mkPostfix(consume(maybeDisp.id), base)
  else
    base
  end
end

#reset ⇒ Object

Resets the state of the parser



404
405
406
 
# File 'lib/Parser.rb', line 404

def reset
  @i = 0
end