Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
A Ruby interpreter for propositional logic
# simple propositional logic
class Token
attr_reader :type, :value
def initialize(type, value)
@type = type
@value = value
end
end
class Lexer
def initialize(input)
@input = input
end
def tokens
@input.split('').map do |char|
# for each `char`, there are only 6 possible things to do
case char
when ' '
next
when '~'
Token.new(:NOT, '~')
when '&'
Token.new(:AND, '&')
when 'v'
Token.new(:OR, 'v')
when '>'
Token.new(:IFSO, '>')
when 'T'
Token.new(:TRUE, 'T')
when 'F'
Token.new(:FALSE, 'F')
end
end.compact
end
end
module AST
class Atom
attr_reader :value
def initialize(value)
@value = value
end
end
class UnaryOperation
attr_reader :operand
def initialize(operand)
@operand = operand
end
end
class BinaryOperation
attr_reader :left, :right
def initialize(left, right)
@left = left
@right = right
end
end
class Negation < UnaryOperation
end
class Conjunction < BinaryOperation
end
class Disjunction < BinaryOperation
end
class Implication < BinaryOperation
end
end
class Parser
def initialize(tokens)
@tokens = tokens
@stream = @tokens.to_enum
@current_token = @stream.next
end
def parse
expression
end
# expression : formula ((AND | OR | IFSO) formula)*
def expression
result = formula
token = @current_token
if token.type == :AND
eat(:AND)
result = AST::Conjunction.new(result, formula)
elsif token.type == :OR
eat(:OR)
result = AST::Disjunction.new(result, formula)
elsif token.type == :IFSO
eat(:IFSO)
result = AST::Implication.new(result, formula)
end
result
end
# formula :: (NOT)? term
def formula
token = @current_token
if token.type == :NOT
eat(:NOT)
return AST::Negation.new(term)
else
return term
end
end
# term :: TRUE | FALSE
def term
token = @current_token
if token.type == :TRUE
eat(:TRUE)
return AST::Atom.new(true)
elsif token.type == :FALSE
eat(:FALSE)
return AST::Atom.new(false)
else
raise "#{token.value} is an invalid term"
end
end
def eat(token_type)
raise 'ERROR' unless @current_token.type == token_type
begin
@current_token = @stream.next
rescue StopIteration
end
end
end
class Interpreter
def initialize(ast)
@ast = ast
end
def interpret
visit(@ast)
end
def visit(node)
if node.is_a? AST::Atom
visit_atom(node)
elsif node.is_a? AST::Negation
visit_negation(node)
elsif node.is_a? AST::Conjunction
visit_conjunction(node)
elsif node.is_a? AST::Disjunction
visit_disjunction(node)
elsif node.is_a? AST::Implication
visit_implication(node)
end
end
def visit_atom(node)
node.value
end
def visit_negation(node)
case visit(node.operand)
when true
false
when false
true
end
end
def visit_conjunction(node)
case [visit(node.left), visit(node.right)]
when [false, false]
false
when [false, true]
false
when [true, false]
false
when [true, true]
true
end
end
def visit_disjunction(node)
case [visit(node.left), visit(node.right)]
when [false, false]
false
when [false, true]
true
when [true, false]
true
when [true, true]
true
end
end
def visit_implication(node)
case [visit(node.left), visit(node.right)]
when [false, false]
true
when [false, true]
true
when [true, false]
false
when [true, true]
true
end
end
end
def interpret(string)
tokens = Lexer.new(string).tokens
ast = Parser.new(tokens).parse
Interpreter.new(ast).interpret
end
# the `interpret` method is what we will eventually build
def assert_interpret_equals(expression, result)
error_msg = "Expected '#{expression}' to evaluate to #{result}"
raise error_msg unless interpret(expression) == result
end
def run_tests
assert_interpret_equals('T', true)
assert_interpret_equals('F', false)
assert_interpret_equals('~T', false)
assert_interpret_equals('~F', true)
assert_interpret_equals('T & T', true)
assert_interpret_equals('T & F', false)
assert_interpret_equals('F & T', false)
assert_interpret_equals('F & F', false)
assert_interpret_equals('T v T', true)
assert_interpret_equals('T v F', true)
assert_interpret_equals('F v T', true)
assert_interpret_equals('F v F', false)
assert_interpret_equals('T > T', true)
assert_interpret_equals('T > F', false)
assert_interpret_equals('F > T', true)
assert_interpret_equals('F > F', true)
assert_interpret_equals('~F & F', false)
assert_interpret_equals('F v ~T', false)
'SUCCESS!'
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment