#LL(1) parser as a solution for exercise 4.9 in "Compiler Construction: Principles and Practice"
#String given is (a,(b,(2)),(c))$
#deduce the grammar ;)
class Parser
def initialize()
@parsing_stack = []
@parsing_stack.push('$')
@parsing_stack.push('lexp-seq')
end
def launch!
introduction
result = nil
until result == :done
print "> "
user_response = gets.chomp
result = parse(user_response)
end
@parsing_stack.inspect
conclusion
end
def parse (input)
output = ""
counter = 0
puts "This is how your stack looks like: \n#{@parsing_stack.inspect}"
input.each_char do |single_char|
case single_char
when '('
while @parsing_stack[-1] != single_char
if @parsing_stack[-1] == 'lexp-seq'
@parsing_stack.pop
@parsing_stack.push('lexp-seq1','lexp')
puts @parsing_stack.inspect
elsif @parsing_stack[-1] == 'lexp'
@parsing_stack.pop
@parsing_stack.push('list')
puts @parsing_stack.inspect
elsif @parsing_stack[-1] == 'list'
@parsing_stack.pop
@parsing_stack.push(')','lexp-seq','(')
puts @parsing_stack.inspect
end
end
if @parsing_stack[-1] == single_char
@parsing_stack.pop
puts @parsing_stack.inspect
output += single_char
counter += 1
puts "read #{counter} characters so far"
end
when 'a','b','c'
while @parsing_stack[-1] != 'identifier'
if @parsing_stack[-1] == 'atom'
@parsing_stack.pop
@parsing_stack.push('identifier')
puts @parsing_stack.inspect
elsif @parsing_stack[-1] == 'lexp'
@parsing_stack.pop
@parsing_stack.push('atom')
puts @parsing_stack.inspect
elsif @parsing_stack[-1] == 'lexp-seq'
@parsing_stack.pop
@parsing_stack.push('lexp-seq1', 'lexp')
puts @parsing_stack.inspect
end
end
if @parsing_stack[-1] == 'identifier'
@parsing_stack.pop
puts @parsing_stack.inspect
output += single_char
counter += 1
puts "read #{counter} characters so far"
end
when '0'..'9'
while @parsing_stack[-1] != 'number'
if @parsing_stack[-1] == 'lexp'
@parsing_stack.pop
@parsing_stack.push('atom')
puts @parsing_stack.inspect
elsif @parsing_stack[-1] == 'atom'
@parsing_stack.pop
@parsing_stack.push('number')
puts @parsing_stack.inspect
elsif @parsing_stack[-1] == 'lexp-seq'
@parsing_stack.pop
@parsing_stack.push('lexp-seq1', 'lexp')
puts @parsing_stack.inspect
end
end
if @parsing_stack[-1] == 'number'
@parsing_stack.pop
puts @parsing_stack.inspect
output += single_char
counter += 1
puts "read #{counter} characters so far"
end
when ')'
while @parsing_stack[-1] != single_char
if @parsing_stack[-1] == 'lexp-seq1'
@parsing_stack.pop
puts @parsing_stack.inspect
end
end
if @parsing_stack[-1] == ')'
@parsing_stack.pop
puts @parsing_stack.inspect
output += single_char
counter += 1
puts "read #{counter} characters so far"
end
when ','
while @parsing_stack[-1] != single_char
if @parsing_stack[-1] == 'lexp-seq1'
@parsing_stack.pop
@parsing_stack.push('lexp-seq')
@parsing_stack.push(',')
puts @parsing_stack.inspect
end
end
if @parsing_stack[-1] == ','
@parsing_stack.pop
puts @parsing_stack.inspect
output += single_char
counter += 1
puts "read #{counter} characters so far"
end
when '$'
while @parsing_stack[-1] != single_char
if @parsing_stack[-1] == 'lexp-seq1'
@parsing_stack.pop
puts @parsing_stack.inspect
end
end
if @parsing_stack[-1] == '$'
@parsing_stack.pop
output += single_char
counter += 1
puts "read #{counter} characters so far"
puts "#{output}"
return :done
end
when "\s"
else
puts "\nInput not recognized!"
end
end
end
def introduction
puts "\n<<< Welcome to the LL(1) Parser >>>\n"
puts "This is an interactive LL(1) Parser for you to play with.\n\n"
end
def conclusion
puts "\n<<< Goodbye and happy parsing! >>>"
end
end
parser = Parser.new()
parser.launch!
