ขุดลึกลงไปใน Ruby Templating:The Parser

วันนี้ เราเดินทางต่อไปยัง Ruby Templating เมื่อมี lexer แล้ว ไปที่ขั้นตอนต่อไป:Parser

ครั้งที่แล้ว เราดูการสอดแทรกสตริง และต่อมา ได้ดำดิ่งสู่การสร้างภาษาเทมเพลตของเราเอง เราเริ่มต้นด้วยการใช้ lexer ที่อ่านเทมเพลตและแปลงเป็นสตรีมของโทเค็น วันนี้ เราจะนำ parser มาใช้งาน นอกจากนี้เรายังจะจุ่มเท้าของเราลงในทฤษฎีภาษาอีกเล็กน้อย

ไปเลย!

ต้นไม้ไวยากรณ์นามธรรม

ลองย้อนกลับไปดูเทมเพลตตัวอย่างง่ายๆ ของเราสำหรับ Welcome to {{name}} . หลังจากใช้ lexer เพื่อสร้างโทเค็นให้กับสตริง เราก็จะได้รายการโทเค็นแบบนี้

Magicbars::Lexer.tokenize("Welcome to {{name}}")
# => [[:CONTENT, "Welcome to "], [:OPEN_EXPRESSION], [:IDENTIFIER, "name"], [:CLOSE]]

ท้ายที่สุด เราต้องการประเมินเทมเพลตและแทนที่นิพจน์ด้วยค่าจริง เพื่อทำให้สิ่งต่าง ๆ มีความท้าทายมากขึ้น เรายังต้องการประเมินนิพจน์บล็อกที่ซับซ้อน เพื่อให้สามารถทำซ้ำและเงื่อนไขได้

ในการทำเช่นนี้ เราต้องสร้างโครงสร้างไวยากรณ์นามธรรม (AST) ที่อธิบายโครงสร้างเชิงตรรกะของเทมเพลต ต้นไม้ประกอบด้วยโหนดที่อาจอ้างอิงโหนดอื่นหรือเก็บข้อมูลเพิ่มเติมจากโทเค็น

สำหรับตัวอย่างง่ายๆ ของเรา ต้นไม้ไวยากรณ์นามธรรมที่ต้องการจะมีลักษณะดังนี้:

การกำหนดไวยากรณ์

ในการกำหนดไวยากรณ์ ให้เริ่มต้นด้วยพื้นฐานทางทฤษฎีของภาษา เช่นเดียวกับภาษาโปรแกรมอื่นๆ ภาษาเทมเพลตของเราเป็นภาษาที่ไม่มีบริบท ดังนั้นจึงสามารถอธิบายได้ด้วยไวยากรณ์ที่ไม่มีบริบท (อย่าปล่อยให้สัญกรณ์ทางคณิตศาสตร์ในคำอธิบายวิกิพีเดียแบบละเอียดทำให้คุณกลัว แนวคิดนี้ค่อนข้างตรงไปตรงมา และมีวิธีการเขียนไวยากรณ์ที่เป็นมิตรกับนักพัฒนามากขึ้น)

ไวยากรณ์ที่ไม่มีบริบทคือชุดของกฎที่อธิบายวิธีสร้างสตริงที่เป็นไปได้ทั้งหมดของภาษา มาดูไวยากรณ์สำหรับภาษาเทมเพลตของเราในรูปแบบ EBNF:

template = statements;
statements = { statement };
statement = CONTENT | expression | block_expression;
expression = OPEN_EXPRESSION, IDENTIFIER, arguments, CLOSE;
block_expression = OPEN_BLOCK, IDENTIFIER, arguments, CLOSE, statements, [ OPEN_INVERSE, CLOSE, statements ], OPEN_END_BLOCK, IDENTIFIER, CLOSE;
arguments = { IDENTIFIER };

การมอบหมายงานแต่ละครั้งจะกำหนดกฎ ชื่อของกฎอยู่ทางด้านซ้าย และกฎอื่นๆ (ตัวพิมพ์เล็ก) หรือโทเค็น (ตัวพิมพ์ใหญ่) จาก lexer ของเราอยู่ทางด้านขวา สามารถเชื่อมกฎและโทเค็นโดยใช้เครื่องหมายจุลภาค , หรือสลับโดยใช้ท่อ | เครื่องหมาย. กฎและโทเค็นภายในวงเล็บปีกกา { ... } อาจจะซ้ำหลายครั้ง เมื่ออยู่ในวงเล็บ [ ... ] ถือว่าไม่บังคับ

ไวยากรณ์ข้างต้นเป็นวิธีที่กระชับในการอธิบายว่าเทมเพลตประกอบด้วยข้อความสั่ง คำสั่งอาจเป็น CONTENT โทเค็น นิพจน์ หรือนิพจน์บล็อก นิพจน์คือ OPEN_EXPRESSION token ตามด้วย IDENTIFIER โทเค็น ตามด้วยอาร์กิวเมนต์ ตามด้วย CLOSE โทเค็น และนิพจน์บล็อกเป็นตัวอย่างที่สมบูรณ์แบบว่าทำไมจึงควรใช้สัญกรณ์แบบด้านบนแทนการพยายามอธิบายด้วยภาษาที่เป็นธรรมชาติ

มีเครื่องมือที่สร้าง parsers โดยอัตโนมัติจากคำจำกัดความของไวยากรณ์เช่นเดียวกับด้านบน แต่ในธรรมเนียม Ruby Magic ที่แท้จริง เรามาสนุกกันและสร้าง Parser ด้วยตัวเอง หวังว่าเราจะได้เรียนรู้อะไรอย่างหนึ่งหรือสองอย่างในกระบวนการนี้

การสร้าง Parser

นอกจากทฤษฎีภาษาแล้ว เรามาเริ่มสร้าง parser กันเลยดีกว่า มาเริ่มกันด้วยเทมเพลตที่น้อยที่สุดแต่ยังคงใช้ได้:Welcome to Ruby Magic . เทมเพลตนี้ไม่มีนิพจน์ใดๆ และรายการโทเค็นประกอบด้วยองค์ประกอบเพียงองค์ประกอบเดียว นี่คือลักษณะ:

[[:CONTENT, "Welcome to Ruby Magic"]]

ขั้นแรก เราตั้งค่าคลาส parser ของเรา ดูเหมือนว่านี้:

module Magicbars
  class Parser
    def self.parse(tokens)
      new(tokens).parse
    end
 
    attr_reader :tokens
 
    def initialize(tokens)
      @tokens = tokens
    end
 
    def parse
      # Parsing starts here
    end
  end
end

คลาสใช้อาร์เรย์ของโทเค็นและจัดเก็บ มีวิธีการสาธารณะเพียงวิธีเดียวที่เรียกว่า parse ที่แปลงโทเค็นเป็น AST

เมื่อมองย้อนกลับไปที่ไวยากรณ์ของเรา กฎที่สำคัญที่สุดคือ template . นั่นก็หมายความว่า parse เมื่อเริ่มกระบวนการแยกวิเคราะห์ จะส่งคืน Template โหนด

โหนดเป็นคลาสธรรมดาที่ไม่มีพฤติกรรมของตนเอง พวกเขาเพียงแค่เชื่อมต่อโหนดอื่นหรือเก็บค่าบางส่วนจากโทเค็น นี่คือสิ่งที่ Template โหนดมีลักษณะดังนี้:

module Magicbars
  module Nodes
    class Template
      attr_reader :statements
 
      def initialize(statements)
        @statements = statements
      end
    end
  end
end

เพื่อให้ตัวอย่างของเราใช้งานได้ เราจำเป็นต้องมี Content โหนด มันแค่เก็บเนื้อหาข้อความ ("Welcome to Ruby Magic" ) จากโทเค็น

module Magicbars
  module Nodes
    class Content
      attr_reader :content
 
      def initialize(content)
        @content = content
      end
    end
  end
end

ต่อไป เรามาใช้วิธี parse เพื่อสร้างอินสแตนซ์ของ Template และตัวอย่าง Content และเชื่อมต่อให้ถูกต้อง

def parse
  Magicbars::Nodes::Template.new(parse_content)
end
 
def parse_content
  return unless tokens[0][0] == :CONTENT
 
  Magicbars::Nodes::Content.new(tokens[0][1])
end

เมื่อเรารัน parser เราจะได้ผลลัพธ์ที่ถูกต้อง:

Magicbars::Parser.parse(tokens)
# => #<Magicbars::Nodes::Template:0x00007fe90e939410 @statements=#<Magicbars::Nodes::Content:0x00007fe90e939578 @content="Welcome to Ruby Magic">>

เป็นที่ยอมรับว่าใช้ได้เฉพาะกับตัวอย่างง่ายๆ ของเราที่มีโหนดเนื้อหาเดียวเท่านั้น ลองเปลี่ยนไปใช้ตัวอย่างที่ซับซ้อนมากขึ้นซึ่งมีนิพจน์อยู่ด้วย:Welcome to {{name}} .

Magicbars::Lexer.tokenize("Welcome to {{name}}")
# => [[:CONTENT, "Welcome to "], [:OPEN_EXPRESSION], [:IDENTIFIER, "name"], [:CLOSE]]

สำหรับสิ่งนี้ เราจำเป็นต้องมี Expression โหนดและ Identifier โหนด Expression โหนดเก็บตัวระบุเช่นเดียวกับอาร์กิวเมนต์ใด ๆ (ซึ่งตามหลักไวยากรณ์เป็นอาร์เรย์ของ Identifier เป็นศูนย์หรือมากกว่า โหนด) เช่นเดียวกับโหนดอื่นๆ ไม่มีอะไรให้ดูที่นี่มากนัก

module Magicbars
  module Nodes
    class Expression
      attr_reader :identifier, :arguments
 
      def initialize(identifier, arguments)
        @identifier = identifier
        @arguments = arguments
      end
    end
  end
end
 
module Magicbars
  module Nodes
    class Identifier
      attr_reader :value
 
      def initialize(value)
        @value = value.to_sym
      end
    end
  end
end

เมื่อโหนดใหม่เข้าที่ เรามาแก้ไข parse วิธีการจัดการทั้งเนื้อหาปกติและนิพจน์ เราทำได้โดยการแนะนำ parse_statements เมธอดที่ยังคงเรียก parse_statement ตราบใดที่มันคืนค่ากลับมา

def parse
  Magicbars::Nodes::Template.new(parse_statements)
end
 
def parse_statements
  results = []
 
  while result = parse_statement
    results << result
  end
 
  results
end

parse_statement ตัวเองเรียก parse_content . ก่อน และหากไม่คืนค่าใด ๆ จะเรียก parse_expression .

def parse_statement
  parse_content || parse_expression
end

คุณสังเกตไหมว่า parse_statement เมธอดเริ่มมีลักษณะคล้ายกับ statement . มาก กฎในไวยากรณ์? ซึ่งการสละเวลาเพื่อเขียนไวยากรณ์อย่างชัดเจนล่วงหน้าจะช่วยได้มากเพื่อให้แน่ใจว่าเรามาถูกทาง

ต่อไป มาแก้ไข parse_content เพื่อไม่ให้ดูเฉพาะโทเค็นแรกเท่านั้น เราทำได้โดยเพิ่ม @position . เพิ่มเติม ตัวแปรอินสแตนซ์ในเครื่องมือเริ่มต้นและใช้เพื่อดึงโทเค็นปัจจุบัน

attr_reader :tokens, :position
 
def initialize(tokens)
  @tokens = tokens
  @position = 0
end
 
# ...
 
def parse_content
  return unless token = tokens[position]
  return unless token[0] == :CONTENT
 
  @position += 1
 
  Magicbars::Nodes::Content.new(token[1])
end

parse_content ตอนนี้เมธอดจะดูที่โทเค็นปัจจุบันและตรวจสอบประเภทของโทเค็น ถ้าเป็น CONTENT โทเค็น จะเพิ่มตำแหน่ง (เนื่องจากแยกวิเคราะห์โทเค็นปัจจุบันเรียบร้อยแล้ว) และใช้เนื้อหาของโทเค็นเพื่อสร้าง Content โหนด หากไม่มีโทเค็นปัจจุบัน (เพราะเราอยู่ที่ส่วนท้ายของโทเค็น) หรือประเภทไม่ตรงกัน วิธีการจะออกก่อนกำหนดและคืนค่า nil .

ด้วยการปรับปรุง parse_content วิธีการ เรามาจัดการกับ parse_expression . ใหม่ วิธีการ

def parse_expression
  return unless token = tokens[position]
  return unless token[0] == :OPEN_EXPRESSION
 
  @position += 1
 
  identifier = parse_identifier
  arguments = parse_arguments
 
  if !tokens[position] || tokens[position][0] != :CLOSE
    raise "Unexpected token #{tokens[position][0]}. Expected :CLOSE."
  end
 
  @position += 1
 
  Magicbars::Nodes::Expression.new(identifier, arguments)
end

ขั้นแรก เราตรวจสอบว่ามีโทเค็นปัจจุบันและประเภทของโทเค็นคือ OPEN_EXPRESSION . หากเป็นกรณีนี้ เราจะไปยังโทเค็นถัดไปและแยกวิเคราะห์ตัวระบุรวมถึงอาร์กิวเมนต์ด้วยการเรียก parse_identifier และ parse_arguments ตามลำดับ ทั้งสองวิธีจะส่งคืนโหนดที่เกี่ยวข้องและเลื่อนโทเค็นปัจจุบัน เมื่อเสร็จแล้ว เรารับรองว่าโทเค็นปัจจุบันมีอยู่และเป็น :CLOSE โทเค็น หากไม่เป็นเช่นนั้น เราแจ้งข้อผิดพลาด มิฉะนั้น เราจะเลื่อนตำแหน่งเป็นครั้งสุดท้าย ก่อนส่งคืน Expression . ที่สร้างขึ้นใหม่ โหนด

ณ จุดนี้ เราเห็นรูปแบบบางอย่างปรากฏขึ้น เรากำลังก้าวไปสู่โทเค็นถัดไปหลายครั้ง และเรากำลังตรวจสอบด้วยว่ามีโทเค็นปัจจุบันและประเภทของโทเค็น เนื่องจากโค้ดนั้นค่อนข้างยุ่งยาก เรามาแนะนำวิธีการช่วยเหลือ 2 วิธีกันเถอะ

def expect(*expected_tokens)
  upcoming = tokens[position, expected_tokens.size]
 
  if upcoming.map(&:first) == expected_tokens
    advance(expected_tokens.size)
    upcoming
  end
end
 
def advance(offset = 1)
  @position += offset
end

expect เมธอดใช้จำนวนตัวแปรของประเภทโทเค็นและตรวจสอบกับโทเค็นถัดไปในสตรีมโทเค็น หากตรงกันทั้งหมด จะข้ามโทเค็นที่ตรงกันและส่งคืน advance วิธีการเพียงแค่เพิ่ม @position ตัวแปรอินสแตนซ์โดยออฟเซ็ตที่กำหนด

สำหรับกรณีที่ไม่มีความยืดหยุ่นเกี่ยวกับโทเค็นที่คาดหวังถัดไป เรายังแนะนำวิธีการที่ทำให้เกิดข้อความแสดงข้อผิดพลาดที่ดีเมื่อโทเค็นไม่ตรงกัน

def need(*required_tokens)
  upcoming = tokens[position, required_tokens.size]
  expect(*required_tokens) or raise "Unexpected tokens. Expected #{required_tokens.inspect} but got #{upcoming.inspect}"
end

โดยใช้วิธีการช่วยเหลือเหล่านี้ parse_content และ parse_expression ตอนนี้สะอาดขึ้นและอ่านง่ายขึ้น

def parse_content
  if content = expect(:CONTENT)
    Magicbars::Nodes::Content.new(content[0][1])
  end
end
 
def parse_expression
  return unless expect(:OPEN_EXPRESSION)
 
  identifier = parse_identifier
  arguments = parse_arguments
 
  need(:CLOSE)
 
  Magicbars::Nodes::Expression.new(identifier, arguments)
end

สุดท้ายนี้ เรามาดูที่ parse_identifier . กัน และ parse_arguments . ด้วยวิธีการช่วยเหลือ parse_identifier วิธีการนั้นง่ายพอ ๆ กับ parse_content กระบวนการ. ข้อแตกต่างเพียงอย่างเดียวคือส่งคืนโหนดประเภทอื่น

def parse_identifier
  if identifier = expect(:IDENTIFIER)
    Magicbars::Nodes::Identifier.new(identifier[0][1])
  end
end

เมื่อดำเนินการ parse_arguments เราสังเกตว่ามันเกือบจะเหมือนกับ parse_statements กระบวนการ. ข้อแตกต่างเพียงอย่างเดียวคือมันเรียก parse_identifier แทน parse_statement . เราสามารถกำจัดตรรกะที่ซ้ำกันได้โดยการแนะนำวิธีการตัวช่วยอื่น

def repeat(method)
  results = []
 
  while result = send(method)
    results << result
  end
 
  results
end

repeat เมธอดใช้ send เพื่อเรียกชื่อเมธอดที่กำหนดจนกว่าจะไม่ส่งคืนโหนดอีกต่อไป เมื่อสิ่งนั้นเกิดขึ้น ผลลัพธ์ที่รวบรวม (หรือเพียงแค่อาร์เรย์ที่ว่างเปล่า) จะถูกส่งกลับ ด้วยตัวช่วยนี้ ทั้ง parse_statements และ parse_arguments กลายเป็นวิธีการแบบบรรทัดเดียว

def parse_statements
  repeat(:parse_statement)
end
 
def parse_arguments
  repeat(:parse_identifier)
end

เมื่อมีการเปลี่ยนแปลงทั้งหมดนี้ เรามาลองแยกวิเคราะห์สตรีมโทเค็นกัน:

Magicbars::Parser.parse(tokens)
# => #<Magicbars::Nodes::Template:0x00007f91a602f910
#     @statements=
#      [#<Magicbars::Nodes::Content:0x00007f91a58802c8 @content="Welcome to ">,
#       #<Magicbars::Nodes::Expression:0x00007f91a602fcd0
#        @arguments=[],
#        @identifier=
#         #<Magicbars::Nodes::Identifier:0x00007f91a5880138 @value=:name>  >

อ่านยากนิดหน่อย แต่อันที่จริง ต้นไม้ไวยากรณ์นามธรรมที่ถูกต้อง Template โหนดมี Content และ Expression คำแถลง. Content ค่าของโหนดคือ "Welcome to " และ Expression ตัวระบุโหนดคือ Identifier โหนดที่มี :name ตามมูลค่าของมัน

การแยกวิเคราะห์นิพจน์ที่ถูกบล็อก

เพื่อให้การติดตั้ง parser ของเราสมบูรณ์ เรายังต้องใช้การแยกวิเคราะห์ของนิพจน์บล็อก โปรดทราบว่านี่คือเทมเพลตที่เราต้องการแยกวิเคราะห์:

Welcome to {{name}}!
 
{{#if subscribed}}
  Thank you for subscribing to our mailing list.
{{else}}
  Please sign up for our mailing list to be notified about new articles!
{{/if}}
 
Your friends at {{company_name}}

ในการดำเนินการนี้ ก่อนอื่นเรามาแนะนำ BlockExpression โหนด แม้ว่าโหนดนี้จะเก็บข้อมูลได้มากกว่าเล็กน้อย แต่ก็ไม่ได้ทำอะไรเลย ดังนั้นจึงไม่น่าตื่นเต้นมาก

module Magicbars
  module Nodes
    class BlockExpression
      attr_reader :identifier, :arguments, :statements, :inverse_statements
 
      def initialize(identifier, arguments, statements, inverse_statements)
        @identifier = identifier
        @arguments = arguments
        @statements = statements
        @inverse_statements = inverse_statements
      end
    end
  end
end

เช่นเดียวกับ Expression โหนด มันเก็บตัวระบุเช่นเดียวกับอาร์กิวเมนต์ใด ๆ นอกจากนี้ยังเก็บคำสั่งของบล็อกและบล็อกผกผัน

เมื่อมองย้อนกลับไปที่ไวยากรณ์ เราสังเกตว่าในการแยกวิเคราะห์นิพจน์ที่บล็อก เราต้องแก้ไข parse_statements เมธอดด้วยการเรียก parse_block_expression . ตอนนี้ดูเหมือนกฎในไวยากรณ์

def parse_statement
  parse_content || parse_expression || parse_block_expression
end

parse_block_expression วิธีการนั้นซับซ้อนกว่าเล็กน้อย แต่ต้องขอบคุณวิธีการช่วยเหลือของเราที่ทำให้อ่านง่าย

def parse_block_expression
  return unless expect(:OPEN_BLOCK)
 
  identifier = parse_identifier
  arguments = parse_arguments
 
  need(:CLOSE)
 
  statements = parse_statements
 
  if expect(:OPEN_INVERSE, :CLOSE)
    inverse_statements = parse_statements
  end
 
  need(:OPEN_END_BLOCK)
 
  if identifier.value != parse_identifier.value
    raise("Error. Identifier in closing expression does not match identifier in opening expression")
  end
 
  need(:CLOSE)
 
  Magicbars::Nodes::BlockExpression.new(identifier, arguments, statements, inverse_statements)
end

ส่วนแรกคล้ายกับ parse_expression . มาก กระบวนการ. มันแยกวิเคราะห์นิพจน์การเปิดบล็อกด้วยตัวระบุและอาร์กิวเมนต์ หลังจากนั้นจะเรียก parse_statements เพื่อแยกวิเคราะห์ด้านในของบล็อก

เมื่อเสร็จแล้ว เราจะตรวจสอบ {{else}} นิพจน์ ระบุโดย OPEN_INVERSE โทเค็นตามด้วย CLOSE โทเค็น หากพบโทเค็นทั้งสอง เราจะเรียก parse_statements อีกครั้งเพื่อแยกวิเคราะห์บล็อกผกผัน มิฉะนั้น เราก็แค่ข้ามส่วนนั้นไปเลย

สุดท้ายนี้ เราตรวจสอบให้แน่ใจว่ามีนิพจน์บล็อกท้ายโดยใช้ตัวระบุเดียวกันกับนิพจน์บล็อกที่เปิดอยู่ หากตัวระบุไม่ตรงกัน เราแจ้งข้อผิดพลาด มิฉะนั้น เราจะสร้าง BlockExpression . ใหม่ โหนดและส่งคืน

การเรียก parser ด้วยโทเค็นของเทมเพลตนิพจน์บล็อกขั้นสูงจะส่งคืน AST สำหรับเทมเพลต ฉันจะไม่รวมเอาท์พุตตัวอย่างไว้ที่นี่ เนื่องจากมันอ่านยาก นี่คือการแสดงภาพของ AST ที่สร้างขึ้นแทน

เพราะเราเรียก parse_statements ภายใน parse_block_expression ทั้งบล็อกและบล็อกผกผันอาจมีนิพจน์มากกว่า นิพจน์บล็อก และเนื้อหาปกติมากขึ้น

การเดินทางยังคงดำเนินต่อไป…

เรามีความก้าวหน้าพอสมควรกับการเดินทางไปสู่การนำภาษาเทมเพลตของเราเองไปใช้ หลังจากศึกษาทฤษฎีภาษามาบ้างแล้ว เราก็ได้กำหนดไวยากรณ์สำหรับภาษาเทมเพลตของเรา และใช้ไวยากรณ์นี้เพื่อนำ parser ไปใช้งานตั้งแต่ต้น

ด้วยทั้ง lexer และ parser เราจึงขาดแค่ตัวแปลเพื่อสร้างสตริงที่สอดแทรกจากเทมเพลตของเรา เราจะกล่าวถึงส่วนนี้ใน RubyMagic ฉบับต่อไป สมัครรับจดหมายข่าวของ Ruby Magic เพื่อรับการแจ้งเตือนเมื่อประกาศออกมา