วันนี้ เราต่อยอดการเดินทางสู่ Ruby Templating ด้วย lexer พร้อมแล้ว มาไปขั้นตอนต่อไป: The parser
ครั้งที่แล้ว เราดู string interpolation และจากนั้น ดำดิ่งสู่การสร้างภาษาเทมเพลตของตัวเอง เราเริ่มด้วยการ implement lexer ที่อ่านเทมเพลตและแปลงเป็น stream ของ tokens วันนี้ เราจะ implement parser ที่ไปกับมัน เราจะจิ้มเท้าลงในทฤษฎีภาษาสักนิด
ไปกันเลย!
Abstract Syntax Trees
มองกลับไปที่ตัวอย่างเทมเพลตง่ายๆ สำหรับ Welcome to {{name}} หลังจากใช้ lexer tokenize สตริง เราได้ list of tokens แบบนี้
Magicbars::Lexer.tokenize("Welcome to {{name}}") # => [[:CONTENT, "Welcome to "], [:OPEN_EXPRESSION], [:IDENTIFIER, "name"], [:CLOSE]]เป้าหมายสุดท้ายคือประเมินเทมเพลตและแทนที่ expression ด้วยค่าจริง เพื่อทำให้ท้าทายมากขึ้น เรายังต้องการประเมิน block expressions ที่ซับซ้อน อนุญาตให้ repetition และ conditionals
เพื่อทำเช่นนี้ เราต้อง generate abstract syntax tree (AST) ที่อธิบายโครงสร้างทางตรรกะของเทมเพลต Tree ประกอบด้วย nodes ที่อาจอ้างอิง nodes อื่นหรือเก็บข้อมูลเพิ่มเติมจาก tokens
สำหรับตัวอย่างง่ายของเรา AST ที่ต้องการมีลักษณะดังนี้:
การกำหนด Grammar
เพื่อกำหนด grammar มาเริ่มจากพื้นฐานทางทฤษฎีของภาษา ในทำนองเดียวกับภาษาโปรแกรมมิ่งอื่นๆ ภาษาเทมเพลตของเราเป็น context-free language และดังนั้นสามารถอธิบายได้ด้วย context-free grammar (อย่าให้ mathematical notations ในคำอธิบาย Wikipedia ที่ละเอียดขนาดนั้นทำให้คุณหนีไป แนวคิดค่อนข้างตรงไปตรงมา และมีวิธีการเขียน grammar ที่ developer-friendly มากกว่า)
Context-free grammar คือชุดกฎที่อธิบายว่า strings ทั้งหมดที่เป็นไปได้ของภาษาถูกสร้างขึ้นอย่างไร มาดู grammar สำหรับภาษาเทมเพลตของเราใน EBNF notation:
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 }; แต่ละ assignment กำหนดกฎ ชื่อกฎอยู่ทางซ้ายและชุดกฎอื่นๆ (lower case) หรือ tokens (upper case) จาก lexer ของเราอยู่ทางขวา กฎและ tokens สามารถ concatenated ได้ด้วย commas , หรือ alternated ด้วย pipe | symbol กฎและ tokens ภายใน curly braces { ... } อาจซ้ำหลายครั้ง เมื่ออยู่ใน brackets [ ... ] ถือว่า optional
Grammar ข้างต้นเป็นวิธีกระชับในการอธิบายว่า template ประกอบด้วย statements statement เป็น token CONTENT expression หรือ block expression Expression เป็น token OPEN_EXPRESSION ตามด้วย token IDENTIFIER ตามด้วย arguments ตามด้วย token CLOSE และ block expression เป็นตัวอย่างสมบูรณ์ของทำไมการใช้ notation เหนียวดีกว่าการพยายามอธิบายด้วยภาษาธรรมชาติ
มี tools ที่ generate parsers จาก grammar definitions แบบข้างต้นโดยอัตโนมัติ แต่ใน true Ruby Magic tradition ให้เราสนุกและสร้าง parser เอง หวังว่าจะเรียนรู้อะไรสักอย่างในกระบวนการ
การสร้าง Parser
ทิ้งทฤษฎีภาษาไว้ข้างข้าง มาก้าวเข้าสู่การสร้าง parser จริง มาเริ่มจากตัวอย่าง minimal แต่ว่างดูที่ยัง valid: Welcome to Ruby Magic เทมเพลตนี้ไม่มี expressions ใดๆ และ list of tokens ประกอบด้วยเพียงหนึ่ง element นี่คือลักษณะ:
[[:CONTENT, "Welcome to Ruby Magic"]]ขั้นแรก เราตั้งค่า parser class มันมีลักษณะดังนี้:
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คลาสรับ array ของ tokens และเก็บไว้ มีเพียง public method เดียวชื่อ parse ที่แปลง tokens เป็น AST
มองกลับที่ grammar กฎ top-most คือ template นั่นบ่งชี้ว่า parse เริ่มต้นกระบวนการ parsing จะคืนค่า node Template
Nodes เป็นคลาสง่ายๆ ไม่มีพฤติกรรมของตัวเอง พวกมันแค่เชื่อม nodes อื่นหรือเก็บค่าบางส่วนจาก tokens นี่คือลักษณะของ node Template:
module Magicbars module Nodes class Template attr_reader :statements def initialize(statements) @statements = statements end end end endเพื่อทำให้ตัวอย่างของเราทำงาน เราต้องการ node Content เช่นกัน มันแค่เก็บ text content ("Welcome to Ruby Magic") จาก token
module Magicbars module Nodes class Content attr_reader :content def initialize(content) @content = content end end end endต่อไป มา implement parse method เพื่อสร้าง instance ของ Template และ instance ของ 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">>ยอมรับว่า นี่ทำงานได้แค่ตัวอย่างง่ายที่มีเพียง content node เดียว มาเปลี่ยนไปตัวอย่างซับซ้อนกว่าที่มี expression จริง: Welcome to {{name}}
Magicbars::Lexer.tokenize("Welcome to {{name}}") # => [[:CONTENT, "Welcome to "], [:OPEN_EXPRESSION], [:IDENTIFIER, "name"], [:CLOSE]]สำหรับนี้ เราต้องการ node Expression และ node Identifier Node Expression เก็บ identifier รวมถึง arguments (ซึ่งตาม grammar เป็น array ของ zero หรือมากกว่า Identifier nodes) ในทำนองเดียวกับ nodes อื่น ไม่มีอะไรมากให้ดู
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ด้วย nodes ใหม่แล้ว มาแก้ไขเมธอด parse ให้จัดการ regular content และ expressions ได้ เราทำโดย introduce เมธอด 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 endparse_statement เองจะเรียก parse_content ก่อน และถ้าไม่คืนค่าอะไร จะเรียก parse_expression
def parse_statement parse_content || parse_expression endคุณสังเกตไหมว่าเมธอด parse_statement เริ่มดูคล้ายกับกฎ statement ใน grammar มากขึ้น นี่คือจุดที่การใช้เวลาเขียน grammar ให้ชัดเจนก่อนช่วยให้เราอยู่บนทางที่ถูกต้องมาก
ต่อไป มาแก้ไขเมธอด parse_content ให้มองไม่แค่ token แรก เราทำโดย introduce instance variable @position เพิ่มเติมใน initializer และใช้มัน fetch current token
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 ตอนนี้มองที่ current token และตรวจสอบประเภท ถ้าเป็น token CONTENT มัน increment position (เพราะ current token ถูก parse สำเร็จ) และใช้ content ของ token สร้าง node Content ถ้าไม่มี current token (เพราะเราอยู่ท้าย tokens) หรือประเภทไม่ตรง เมธอดจะ exit early และคืน 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ขั้นแรก ตรวจสอบว่ามี current token และประเภทคือ OPEN_EXPRESSION ถ้าใช่ เรา advance ไป token ถัดไป และ parse identifier รวมถึง arguments โดยเรียก parse_identifier และ parse_arguments ตามลำดับ ทั้งสองเมธอดจะคืนค่า nodes ตามลำดับและ advance current token เมื่อเสร็จแล้ว เรา ensure ว่า current token มีอยู่และเป็น token :CLOSE ถ้าไม่ใช่ raise error ไม่เช่นนั้น advance position อีกครั้งสุดท้าย ก่อนคืนค่า Expression node ใหม่
ณ จุดนี้ เราเห็นบาง patterns Emerged เรา advance ไป token ถัดไปหลายครั้ง และเราตรวจสอบว่ามี current token และประเภทของมัน เนื่องจากโค้ดสำหรับนั้นค่อนข้าง cumbersome มา introduce สอง helper methods
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 รับจำนวน token types แบบ variable และตรวจสอบกับ tokens ถัดไปใน token stream ถ้าทั้งหมด match มัน advance ผ่าน matching tokens และคืนค่าพวกมัน เมธอด advance เพียง increment instance variable @position ด้วย offset ที่ให้มา
สำหรับกรณีที่ไม่มี flexibility เกี่ยวกับ next expected token เรายัง introduce เมธอดที่ raise error message ที่ดีเมื่อ token ไม่ match
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ด้วยการใช้ helper methods เหล่านี้ 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 ด้วย helper methods parse_identifier เรียบง่ายเท่ากับ parse_content ความแตกต่างเดียวคือคืนค่าประเภท node อื่น
def parse_identifier if identifier = expect(:IDENTIFIER) Magicbars::Nodes::Identifier.new(identifier[0][1]) end endเมื่อ implement เมธอด parse_arguments เราสังเกตว่ามันเกือบเหมือน parse_statements สมบูรณ์แบบ ความแตกต่างเดียวคือมันเรียก parse_identifier แทน parse_statement เราสามารถกำจัด logic ซ้ำได้โดย introduce helper method อีกตัว
def repeat(method) results = [] while result = send(method) results << result end results endเมธอด repeat ใช้ send เรียก method name ที่ให้มา จนกว่าจะไม่คืนค่า node อีกแล้ว เมื่อเกิดขึ้น results ที่เก็บรวบรวม (หรือแค่ empty array) จะถูกคืนค่า ด้วย helper นี้ ทั้ง parse_statements และ parse_arguments กลายเป็น one-line methods
def parse_statements repeat(:parse_statement) end def parse_arguments repeat(:parse_identifier) endด้วยการเปลี่ยนแปลงทั้งหมดนี้ มาลอง parse token stream:
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> >อ่านยากหน่อย แต่จริงๆ แล้วเป็น AST ที่ถูกต้อง Node Template มี Content และ Expression statement Node Content มีค่า "Welcome to " และ node Expression มี identifier เป็น node Identifier ที่มีค่า :name
Parsing Block Expressions
เพื่อให้ parser implementation สมบูรณ์ เรายังต้อง implement parsing of block expressions ตามที่ระบุ นี่คือเทมเพลตที่เราต้องการ parse:
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}}เพื่อทำเช่นนี้ มา introduce node BlockExpression ก่อน แม้ node นี้จะเก็บข้อมูลมากกว่า แต่ไม่ทำอะไรเพิ่มเติม จึงไม่ค่อย exciting
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เช่นเดียวกับ node Expression มันเก็บ identifier และ arguments เพิ่มเติม มันยังเก็บ statements ของ block และ inverse block
มองกลับที่ grammar เราสังเกตว่าต้องแก้ไขเมธอด parse_statements ด้วยการเรียก parse_block_expression ตอนนี้มันดูเหมือนกฎใน grammar สมบูรณ์
def parse_statement parse_content || parse_expression || parse_block_expression endเมธอด parse_block_expression เองค่อนข้างซับซ้อน แต่ขอบคุณ helper methods ของเรา มันยังอ่านง่าย
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 opening block expression พร้อม identifier และ arguments หลังจากนั้น เรียก parse_statements เพื่อ parse ภายใน block
เมื่อเสร็จแล้ว เราตรวจสอบ {{else}} expression ที่ระบุโดย token OPEN_INVERSE ตามด้วย CLOSE ถ้าทั้งสอง token พบ เราเรียก parse_statements อีกครั้งเพื่อ parse inverse block ไม่เช่นนั้น เราแค่ข้ามส่วนนั้นไปเลย
ในที่สุด เรา ensure ว่ามี end block expression ด้วย identifier เดียวกับ open block expression ถ้า identifiers ไม่ตรง raise error ไม่เช่นนั้น สร้าง BlockExpression node ใหม่และคืนค่า
การเรียก parser ด้วย tokens ของ advanced block expression template จะคืน AST สำหรับเทมเพลต ผมจะไม่รวม example output ที่นี่ เพราะอ่านเกือบไม่ออก แทนที่จะเป็น visual representation ของ AST ที่สร้างขึ้น
เพราะเราเรียก parse_statements ภายใน parse_block_expression ทั้ง block และ inverse block อาจรวม expressions, block expressions, และ regular content เพิ่มเติมได้
การเดินทางต่อไป…
เราทำความคืบหน้าที่ดีกับการเดินทางสู่การ implement ภาษาเทมเพลตของตัวเอง หลังจากดुबเท้าลงทฤษฎีภาษาสั้นๆ เรากำหนด grammar สำหรับภาษาเทมเพลตของเราและใช้มัน implement parser จากศูนย์
ด้วย lexer และ parser พร้อมแล้ว เราขาดแค่ interpreter เพื่อ generate interpolated string จากเทมเพลตของเรา เราจะครอบคลุมส่วนนี้ใน RubyMagic ออกแบบหน้า สมัครรายชื่อ Ruby Magic mailinglist เพื่อได้รับแจ้งเมื่อออก
