Парсим HTML Zen на F#, FsLex и FsYacc

Все наверное так или иначе слышали про HTML Zen и про то, как он спасает при написании HTML. Но мало кому приходит в голову написать свою собственную реализацию, когда есть готовая на Python’е. На самом деле, собственная реализация позволяет добавлять собственные конструкты, нужные только вам.

Давайте попробуем реализовать базовые конструкты HTML Zen. Для этого мы воспользуемся языком F#, библиотекой тестирования FSunit. Будем писать программу в стиле TDD. Я пожалуй назову ее FSharpZen, так интересней.

Исходный код можно найти тут: https://bitbucket.org/nesteruk/fsharpzen

Базовые случаи

Весь HTML Zen – это набор трансформаций. Например, на входе a, а на выходе <a href="|"></a>, где | обозначает финальное положение каретки. Следовательно, можно как минимум написать следующий тест:

[<TestFixture>]
type ``Basic transformation tests`` ()=
  [<Test>] member test.
    ``Empty input should yield empty output`` () =
      Zen.html "" |> should equal "|"

Это счастье совсем не компилируется, поэтому нам придется как минимум предоставить хоть какую-то реализацию, например:

module FSharpZen.Zen
let html input = ""

В результате, конечно, получим “красный” тест:

Expected string length 1 but was 0. Strings differ at index 0.
Expected: "|"
But was:  <string.Empty>
-----------^

Ну а дальше мы “жульничаем” и наш тест проходит. Не забываем сказать спасибо Решарперу, который поддерживает F#-тесты out-of-the-box.

Пустые тэги

Дефолтное поведение HTML Zen такое, что при написании, скажем, буквы z разворачивается шаблон <z>|</z>. С другой стороны, hr определенно превращается в <hr/>|, а img – в <img src="|"></img>.

[<Test>] member test.
  ``Simple entity should be in a closed tag`` () =
    Zen.html "c" |> should equal "<c>|</c>"
[<Test>] member test.
  ``Self-closing entity should yield a self-closing tag`` () =
    Zen.html "br" |> should equal "<br/>|"
[<Test>] member test.
  ``Entity should have appropriate attributes generated and placeholder set accordingly`` () =
    Zen.html "a" |> should equal "<a href=\"|\" title=\"\"></a>"

Теперь у нас есть 3 use-case’а: просто тэги, тэги которые не нуждаются в закрывающем тэге, и тэги которые имеют сложную начинку. Второй и третий случай – специальные, поэтому мы можем попробовать их выделить…

let singularEntities = ["hr"; "br"; "img"]
let neededAttributes = [
                         "a", ["href", "title"];
                         "img", ["src", "alt"]
                       ]

TDD по наивности своей рекоммендует “самое простое работающее решение” которое в нашем случае выглядит примерно вот так:

let html input =
  if input |> String.IsNullOrEmpty then "|"
  else
    let sb = StringBuilder()
    sb.Append ("<" + input) |> ignore
    for a in neededAttributes do
      match a with
      | i, attributes when i = input ->
        let firstAtt = List.head attributes
        sb.Append(" " + firstAtt + "=\"|\"") |> ignore
        attributes |> List.tail 
                   |> List.iter (fun f -> sb.Append(" " + f + "=\"\"") |> ignore)
      | _ -> ()
    // see if this is a self-closing tag
    let isSelfClosing = List.exists (fun f -> f = input) singularEntities
    let pipe = if sb.ToString().Contains("|") then "" else "|"
    sb.Append(if isSelfClosing then "/>" + pipe else ">" + pipe + "</" + input + ">") |> ignore
    sb.ToString()

До элегантности тут как до Китая. Вывода напрашивается два:

• Нужны какие-то структуры для того чтобы отражать структуру тэгов, особенно когда будут вложенные, с аттрибутами, и т.д.
• Нужно учиться лучше парсить строки. То, что мы делаем выше – “не по паттернам”.

FsLex и FsYacc

Лучший способ парсить – это взять что-то уже готовое (хотя до меня это иногда туго доходит). Поэтому для парсинга наших магических строк мы возьмем F# Power Pack, и скачаем через VS Extension Manager шаблон проекта под названием F# Parser Language Starter. Это позволит нам получить пример, в котором есть три важных файла, а именно:

• Ast.fs — определение синтактического дерева. В нашем случае оно достаточно простое.
• Lexer.fsl — определение “лексем”, т.е. различных кусков строки, которые формируют выражение HTML Zen.
• Parser.fsy — собственно парсер, который определяет то, как лексемы становятся чем-то осмысленным.

В сгенерированном примере получается калькулятор¹, нам же остается только поменять его чтобы начали поддерживаться наши собственные структуры.

AST

Итак, для нашего магического синтаксиса нам нужно определить тот набор элементов дерева, который мы фактически готовы подерживать. Это включает в себя как минимум следующие конструкции²:

• Идентификаторы, такие как div, href и так далее. Они парсятся “как есть”.
• Классы, т.е. при при написании a.b мы получаем <a href="|" class="b"></a>.
• Идентификаторы, т.е. a#b ставовится <a id="b" href="|"></a>.
• Множители, т.е. hr*2 дает нам <hr/><hr/>. Между тэгами, между прочим, фигурирует \n – это вынужденная мера для таких ситуаций как ol>li*2.
• Вложенные тэги – например, ol+li становится <ol><li>|</li></ol>, с соответствующими переносами и отступами.

Теперь попробуем перевисти все эти идеи на структуры F#. У меня получилось примерно следующее:

type ZenExpression =
  | ZenExpression of Expression list
and Expression =
  | Expression of Identifier * Qualifier list
and Identifier =
  | Identifier of string
and Qualifier =
  | ClassQualifier of string
  | IdentityQualifier of string
  | CardinalityQualifier of int

Строго говоря, то, что вы видите выше – уродство. С этим очень сложно работать. К тому же, нет никаких ограничений на количество идентификатов или показателей размерности (а ведь элемент может иметь только один квалификатор каждого типа). Ну да ладно, эту проблему мы разрулим позже.

Лексер

Лексер у нас будет простенький. Во-первых, нужно определить регулярные выражения для всех полезных конструктов:

let digit = ['0'-'9']
let letter = ['a'-'z'] | ['A'-'Z']
let letterOrDigit = letter | digit
let whitespace = [' ' '\t' ]
let newline = ('\n' | '\r' '\n')

Ну а теперь, нужно определить какие конструкты будут производится из регулярных выражений. Нам нужны:

• Строки (возможно с числами) для идентификаторов и квалификаторов.
• Операторы для разделения квалификаторов (., #, + и *)
• Числа для квалификатора размерности

Следовательно, получаем следующее определение:

rule tokenize = parse
| whitespace	   { tokenize lexbuf }
| newline        { tokenize lexbuf }
| letterOrDigit+ { STRING(lexeme lexbuf) }
| digit+         { INT32(Int32.Parse(lexeme lexbuf)) }
// Operators
| "+"            { PLUS }
| "#"            { HASH }
| "*"            { TIMES }
| "."            { DOT }
// EOF
| eof   { EOF }

Парсер

Определив лексемы, нам нужно научиться парсить их и превращать их комбинации в элементы AST. Для этого пойдет следующее определение:

start: exprs { ZenExpression($1) }
exprs:
  | exp PLUS exprs EOF { Expression($1) :: $3 }
  | exp EOF { [Expression($1)] }
exp:
  | STRING quals { (Identifier($1), $2) }
  | STRING { (Identifier($1), []) }
quals:
  | qual quals { $1 :: $2 }
  | qual { [$1] }
qual:
  | DOT STRING  { ClassQualifier($2) }
  | HASH STRING { IdentityQualifier($2) }
  | TIMES INT32 { CardinalityQualifier($2) }

Помимо того, что списки чего бы то ни было создаются рекурсивно, тут нет ничего необычного.

Принтер

Ну а теперь самое сложное. Помните я сказал, что та структура в которую мы парсим – убогая и избыточная? Так вот, сейчас вы увидите насколько неудобно такую штуку печатать.

Во-первых, код забрасывается кучей вспомогательных функций для поиска квалификаторов определенного типа. Например:

let rec private getId qualifierList =
  match qualifierList with
  | IdentityQualifier(id) :: t -> Some(id)
  | h :: t -> getId t
  | [] -> None

Потом, приходится (не знаю в какой уже раз) делать вменяемый билдер для кода:

type CodeBuilder() =
  let sb = StringBuilder()
  let mutable indent = 0;
  member this.GetIndent() =
    System.String.Empty.PadRight(indent * 2)
  member this.AppendWithIndent (text:string) = 
    sb.Append(this.GetIndent()).Append(text) |> ignore
  member this.Append (text:string) = 
    sb.Append(text) |> ignore
  member this.NewLine() = sb.AppendLine() |> ignore
  member this.Indent() = indent <- indent + 1
  member this.Unindent() = indent <- indent - 1
  override this.ToString() = sb.ToString()

Потом нужен поистине гигантский кусок кода для того чтобы распарсить все кейсы – конструкция весьма громоздкая:

let rec private print expressions (builder:CodeBuilder) =
  match expressions with
  | h :: t ->
    builder.AppendWithIndent "<"
    match h with
    | Expression(name, qual) ->
      builder.Append name
      // id it if has any
      match getId qual with
      | Some(id) -> builder.Append(" id=\"" + id + "\"")
      | _ -> ()
      // needed attributes
      let needed = getNeededAttributes name
      needed |> List.iter(fun n -> builder.Append(" " + n + "=\"|\""))
      // classes
      let classes = getClasses qual
      if classes <> List.empty then
        builder.Append(" class=\"")
        builder.Append(System.String.Join(" ", classes))
        builder.Append("\"")
      // if self-closing, then close it
      let selfClosing = singularEntities |> List.exists(fun f -> f = name)
      if selfClosing then builder.Append "/>|"
      else builder.Append ">"
      // if there's more stuff in there, add it
      if t <> List.empty then
        builder.Indent()
        builder.NewLine()
        print t builder
        builder.NewLine()
        builder.Unindent()
        
      if not selfClosing then
        builder.Append("|</" + name + ">")
  | _ -> 
    builder.Append "|"

А вот собственно как все запускается:

let html input = 
  let lexbuf = LexBuffer<char>.FromString(input)
  let parsed = Parser.start Lexer.tokenize lexbuf
  let builder = new CodeBuilder()
  match parsed with
  | ZenExpression(items) -> print items builder
  let pre = builder.ToString() |> Seq.toList
  let rec clean input metBar =
    match input with
    | '|' :: t when not metBar -> '|' :: clean t true
    | '|' :: t when metBar -> clean t true
    | h :: t -> h :: clean t metBar
    | [] -> []
  let lst = clean pre false
  System.String(lst |> List.toArray)

Излишние телодвижения у нас от того, что мы в принтере генерируем избыточное число кареток. Нужно удалить все кроме первой, а более элегантного способа я не знаю (хотя не исключаю что он существует).

Заключение

В очередной раз у меня сомнения. Количество телодвижений для того чтобы реализовать парсер примерно в 10 раз больше чем когда я все это писал “в лоб” на C#. FxLex и FsYacc обладают практически нулевой диагностичностью, никакого IntelliSense нет, такое впечатление что блуждаешь в потемках. Что касается принтера, опять же, структура на которую все было “замэплено” очень неудобна; намного быстрее было бы использовать ООП. Плюшки FP вроде паттерн-матчинга и прочего тут совсем не амортизировались.

Заметки

1. ↑ Кстати, пример кривой – попробуйте например ввести 2-2 и у вас парсер моментально накроется – а все из-за попытки взять минус перед 2кой как префикс-оператор. :)
2. ↑ Тут я немного отклонился от “кошерного” HTML Zen который, на мой взгляд, достаточно избыточен. В частности, я заменил > на + а “оригинальный” + попросту проигнорировал.