1. ホーム
  2. スクリプト・コラム
  3. ルア

Luaで式を解析するためのディープダイブ

2022-02-09 01:34:07

 パターンを使用する

この例では、スキーマを作成し使用するための、非常にシンプルだが完全な手順である

コピーコード コードは以下の通りです。
local lpeg = require "lpeg"

-- matches a word followed by end-of-string
p = lpeg.R"az"^1 * -1

print(p:match("hello")) --> 6
print(lpeg.match(p, "hello")) --> 6
print(p:match("1 hello")) --> nil

パターンは単純に1文字以上の小文字の並びで、末尾は(-1)である。このプログラムでは、メソッドと関数としてmatchを呼び出している。上の成功例では、match関数は、マッチングに成功した最初の文字のインデックスを返し、その文字列の長さに1を足す。

コピーコード コードは以下の通りです。
Name-value lists

この例では、名前と値のペアのリストを解析し、それらのペアのテーブルを返します。

コピーコード コードは以下の通りです。
lpeg.locale(lpeg) -- adds locale entries into 'lpeg' table

local space = lpeg.space^0
local name = lpeg.C(lpeg.alpha^1) * space
local sep = lpeg.S(",;") * space
local pair = lpeg.Cg(name * "=" * space * name) * sep^-1
local list = lpeg.Cf(lpeg.Ct("") * pair^0, rawset)
t = list:match("a=b, c = hi; next = pi") --> { a = "b", c = "hi", next = "pi" }

各ペアには、formatname =namefollowed のセパレータ(カンマまたはセミコロン)をオプションで指定できます。  pairpatternはグループパターン内でクロージャを形成し、それらの名前は個別にキャプチャされた値になることができます。次にlistpatternは、これらのキャプチャを折りたたみます。rawsetreturns((uninitialized set)) はテーブルそのものを返すので、アキュムレータは常にテーブル内で実行されます。


次のコードは、与えられたセパレータパターンsepをセパレータとして使用し、文字列を分割するパターンを作成します。

コピーコード コードは以下の通りです。
function split (s, sep)
  sep = lpeg.P(sep)
  local elem = lpeg.C((1 - sep)^0)
  local p = elem * (sep * elem)^0
  return lpeg.match(p, s)
end

まず、この関数はsepが適切なパターンであることを確認します。マッチするセパレータがない限り,パターンのelemは0文字以上の任意の文字の重複となる。また,そのマッチング値も取り込む。パターンpは,sepで分割された要素の集合にマッチする。

分割の結果得られる値が多すぎると、Luaの関数が返す値の最大数をオーバーしてしまう場合があります。この場合、値をテーブルに入れるのは

コピーコード コードは以下の通りです。
function split (s, sep)
  sep = lpeg.P(sep)
  local elem = lpeg.C((1 - sep)^0)
  local p = lpeg.Ct(elem * (sep * elem)^0) -- make a table capture
  return lpeg.match(p, s)
end

パターン検索

基本的なマッチングは、アンカー付きパターンでしか機能しません。もし、文字列のどこかにマッチするパターンを見つけたいのであれば、どこかにマッチするパターンを書かなければなりません。

パターンは書き込み可能なので、任意のパターンpを与えると、pが文字列のどこかにマッチするかを検索して新しいパターンを返す関数を書くことができる。この検索を行うにはいくつかの方法がある。そのひとつは次のような方法である。

コピーコード コードは以下の通りです。
function anywhere (p)
  return lpeg.P{ p + 1 * lpeg.V(1) }
end

この構文を素直に読むと、pをマッチさせるか、文字をスキップして再度マッチさせるか、ということになります。

もし、文字列中のパターンのすべてのマッチング位置(文字列中の特定の位置にあるということだけでなく)を知りたい場合は、パターンに位置捕捉を追加します。

コピーコード コードは以下の通りです。
local I = lpeg.Cp()
function anywhere (p)
  return lpeg.P{ I * p * I + 1 * lpeg.V(1) }
end

print(anywhere("world"):match("hello world!")) -> 7 12

この検索に対する別のアプローチとして、次のようなものがある。

コピーコード コードは以下の通りです。
local I = lpeg.Cp()
function anywhere (p)
  return (1 - lpeg.P(p))^0 * I * p * I
end

ここでもこのパターンの素直な解釈:pにマッチしないときは、できるだけ多くの文字をスキップして、pにマッチする(さらに正しい位置のキャプチャをする)。

もし、単語の境界だけにマッチするパターンを探すのであれば、次のような変換が使えるだろう。

コピーコード コードは以下の通りです。
local t = lpeg.locale()

function atwordboundary (p)
  return lpeg.P{
    [1] = p + t.alpha^0 * (1 - t.alpha)^1 * lpeg.V(1)
  }
end

バランスの取れたブラケット

次のパターンは、バランスブラケットを含む文字列のみにマッチします: :

コピーコード コードは以下の通りです。
b = lpeg.P{ "(" * ((1 - lpeg.S"()") + lpeg.V(1))^0 * ")" }

最初に(そして唯一)与えられた構文規則を読むと、いわゆるバランス文字列とは、開き括弧の後に0個以上の非括弧文字またはバランス文字列(LPFG.V(1))が続き、最後に開き括弧で閉じることができる閉じ括弧が続くものであることがわかります。
グローバル置換

次の例は、tostring.gsubが行うのと同様の作業を行うものです。これは、親文字列をパターンと置換値で受け取り、渡された親文字列のうち指定されたパターンにマッチするすべての部分文字列を、指定された置換値で置き換えます: :

コピーコード コードは以下の通りです。
function gsub (s, patt, repl)
  patt = lpeg.P(patt)
  patt = lpeg.Cs((patt / repl + 1)^0)
  return lpeg.match(patt, s)
end

instring.gsubと同様に、置換値には文字列、関数、テーブルのいずれかを指定することができます。

カンマ区切り値(CSV)

次の例では、文字列をカンマ区切り値に変換し、すべてのフィールドを返します。

コピーコード コードは以下の通りです。
local field = '"' * lpeg.Cs(((lpeg.P(1) - '"') + lpeg.P'""' / '"')^0) * '"' +
                    lpeg.C((1 - lpeg.S',\n"')^0)

local record = field * (',' * field)^0 * (lpeg.P'\n' + -1)

function csv (s)
  return lpeg.match(record, s)
end

フィールドは、引用フィールド(ファミリーにはシングルクォート、ダブルクォート以外の任意の文字を含むことができる)または非引用フィールド(カンマ、改行、クォートを含まない)のいずれかです。レコードは、カンマで区切られたフィールドのリストである(改行があるか、文字列で終わるか)。

このように、直前のマッチで返された各フィールドが独立して返されます。定義されたレコードを横取りするリストを追加した場合。返されるのは、もはやすべてのフィールドを含む独立したリストではなくなります。

コピーコード コードは以下の通りです。
local record = lpeg.Ct(field * (',' * field)^0) * (lpeg.P'\n' + -1)


UTF-8とラテン語1

LPeg を使って文字列を UTF-8 エンコーディングから Latin 1 (ISO 88590-1) に変換するのは難しいことではありません。

コピーコード コードは以下の通りです。
-- convert a two-byte UTF-8 sequence to a Latin 1 character
local function f2 (s)
  local c1, c2 = string.byte(s, 1, 2)
  return string.char(c1 * 64 + c2 - 12416)
end

local utf8 = lpeg.R("\0\127")
           + lpeg.R("\194\195") * lpeg.R("\128\191") / f2

local decode_pattern = lpeg.Cs(utf8^0) * -1

これらのコードにおけるUTF-8の定義は、すでにLatin 1のエンコーディング範囲(0から255まで)になっています。その範囲にないすべてのエンコーディング(および無効なエンコーディング)は、パターンにマッチしません。

decode_patternが要求するように、このパターンはすべての入力にマッチし(-1が末尾にあるので)、無効な文字列は問題についての有益な情報がないまま、マッチに失敗することになる。decode_patternを以下のように再定義することで、この状況を改善することができる。

コピーコード コードは以下の通りです。
local function er (_, i) error("invalid encoding at position " . i) end

local decode_pattern = lpeg.Cs(utf8^0) * (-1 + lpeg.P(er))

さて、パターンutf8^0が文字列の終端より前に停止した場合、該当するエラー関数が呼び出されます。

UTF-8とユニコード

前のパターンを拡張して、すべての Unicdoe コード フラグメントを処理することができますが、もちろん、アラビア数字の 1 やその他のバイトエンコーディングに変換することはできません。その代わりに、シーケンス結果の数字で表されるコードフラグメントを翻訳するのです。以下がそのコードである。

コピーコード コードは以下の通りです。
-- decode a two-byte UTF-8 sequence
local function f2 (s)
  local c1, c2 = string.byte(s, 1, 2)
  return c1 * 64 + c2 - 12416
end
-- decode a three-byte UTF-8 sequence
local function f3 (s)
  local c1, c2, c3 = string.byte(s, 1, 3)
  return (c1 * 64 + c2) * 64 + c3 - 925824
end
-- decode a four-byte UTF-8 sequence
local function f4 (s)
  local c1, c2, c3, c4 = string.byte(s, 1, 4)
  return ((c1 * 64 + c2) * 64 + c3) * 64 + c4 - 63447168
end
local cont = lpeg.R("\128\191") -- continuation byte
local utf8 = lpeg.R("\0\127") / string.byte
           + lpeg.R("\194\223") * cont / f2


-- decode a two-byte UTF-8 sequence
local function f2 (s)
  local c1, c2 = string.byte(s, 1, 2)
  return c1 * 64 + c2 - 12416
end
-- decode a three-byte UTF-8 sequence
local function f3 (s)
  local c1, c2, c3 = string.byte(s, 1, 3)
  return (c1 * 64 + c2) * 64 + c3 - 925824
end
-- decode a four-byte UTF-8 sequence
local function f4 (s)
  local c1, c2, c3, c4 = string.byte(s, 1, 4)
  return ((c1 * 64 + c2) * 64 + c3) * 64 + c4 - 63447168
end
local cont = lpeg.R("\128\191") -- continuation byte
local utf8 = lpeg.R("\0\127") / string.byte
           + lpeg.R("\194\223") * cont / f2

Lua用の長い文字列

Luaの長い文字列は、パターン[= *[]で始まり、全く同じ数の等号を持つ[ =*]の最初の出現で終わります。開始括弧の後に改行文字がある場合、改行文字は破棄されます(つまり、文字列の一部として扱われません)。

Luaで長い文字列にマッチするには、最初に繰り返される等号をパターンに取り込み、その後、単純に閉じた文字列の候補を探し、同じ数の等号を持つかどうかをチェックする必要があります。

コピーコード コードは以下の通りです。
equals = lpeg.P"="^0
open = "[" * lpeg.Cg(equals, "init") * "[" * lpeg.P"\n"^-1
close = "]" * lpeg.C(equals) * "]"
closeeq = lpeg.Cmt(close * lpeg.Cb("init"), function (s, i, a, b) return a == b end)
string = open * lpeg.C((lpeg.P(1) - closeeq)^0) * close / 1

closeパターンは[=*[]にマッチし、同じく重複する等号をinitというグループ内で捕捉します。closeeqパターンはまずcloseにマッチし、次にopenとinitというグループ内で以前に捕捉した内容を逆捕捉して復元します。文字列パターンはopenで始まった後、closeeqにマッチするまで含み、最終的にcloseにマッチする。最後の数値キャプチャは、単にcloseで生成されたキャプチャを破棄する。

算術式

この例では、単純な算術式を完全に解析して評価します。そして、それを2つのスタイルで記述します。

最初のルートは、まず構文木を構築し、その木をトラバースして式の値を計算する。

コピーコード コードは以下の通りです。
-- Dictionary element
[code]local Space = lpeg.S(" \n\t")^0
local Number = lpeg.C(lpeg.P"-"^-1 * lpeg.R("09")^1) * Space
local TermOp = lpeg.C(lpeg.S("+-")) * Space
local FactorOp = lpeg.C(lpeg.S("*/")) * Space
local Open = "(" * Space
local Close = ")" * Space

-- Syntax
local Exp, Term, Factor = lpeg.V"Exp", lpeg.V"Term", lpeg.V"Factor"
G = lpeg.P{ Exp,
  Exp = lpeg.Ct(Term * (TermOp * Term)^0);
  Term = lpeg.Ct(Factor * (FactorOp * Factor)^0);
  Factor = Number + Open * Exp * Close;
}

G = Space * G * -1

-- Valuator
function eval (x)
  if type(x) == "string" then
    return tonumber(x)
  else
    local op1 = eval(x[1])
    for i = 2, #x, 2 do
      local op = x[i]
      local op2 = eval(x[i + 1])
      if (op == "+") then op1 = op1 + op2
      elseif (op == "-") then op1 = op1 - op2
      elseif (op == "*") then op1 = op1 * op2
      elseif (op == "/") then op1 = op1 / op2
      end
    end
    return op1
  end
end

-- parsing/valuing
function evalExp (s)
  local t = lpeg.match(G, s)
  if not t then error("syntax error", 2) end
  return eval(t)
end

-- Example of use
print(evalExp"3 + 5*9 / (1+1) - 12") --> 13.5

2番目のスタイルは、構文ツリーを構築せず、直接評価します。次のコードはこのパスに従います(上記と同じ辞書要素を想定しています)。

コピーコード コードは以下の通りです。
-- helper function
function eval (v1, op, v2)
  if (op == "+") then return v1 + v2
  elseif (op == "-") then return v1 - v2
  elseif (op == "*") then return v1 * v2
  elseif (op == "/") then return v1 / v2
  end
end

-- Syntax
local V = lpeg.
G = lpeg.P{ "Exp",
  Exp = lpeg.Cf(V"Term" * lpeg.Cg(TermOp * V"Term")^0, eval);
  Term = lpeg.Cf(V"Factor" * lpeg.Cg(FactorOp * V"Factor")^0, eval);
  Factor = Number / tonumber + Open * V"Exp" * Close;
}

-- Usage examples
print(lpeg.match(G, "3 + 5*9 / (1+1) - 12")) --> 13.5

フォールド(コレクター)キャプチャーを使用していることに注意してください。式の値を計算するために、コレクタは最初の項の値から始めて、コピーするたびに進化したコレクタ、演算子、新しい項を適用します。