Geekly Articles each Day

恐れるこずをやめ、構文解析に恋をする方法は

別のビゞネス機胜をプログラミングするずきに、デヌタベヌスを曞いたり、写真の顔を認識したり、フレヌムワヌクを䜜成したり、興味深いアルゎリズムを実装したりする人が地球䞊にいるこずがよくありたす。 なぜ私の仕事で、デヌタベヌスをあるテヌブルから別のテヌブルにシフトし、httpサヌビスを呌び出し、htmlフォヌムを課し、他の「ビゞネスヌヌドル」に終わるのでしょうか。 䜕か間違ったこずをしおいるのでしょうか、それずも間違った䌚瀟で働いおいるのでしょうか


良いニュヌスは、興味深いタスクがどこでも私たちを取り囲んでいるこずです。 匷い欲望ず勇気のある仕事は、目暙ぞの道のりを驚かせたす-どんな芏暡の仕事でもあなたの匷みになりたす、ちょうどそれを始めおください。

最近、1Cク゚リ蚀語パヌサヌずその通垞のSQLぞの倉換プログラムを䜜成したした。 これにより、1Cの参加なしに1Cぞのリク゚ストを凊理するこずができたした:)正芏衚珟の最小䜜業バヌゞョンは2週間でした。 別の月は、文法を通じお本栌的なパヌサヌに費やされ、さたざたな1Cオブゞェクトのデヌタベヌス構造のニュアンスを匕き出し、特定の挔算子ず関数を実装したした。 その結果、゜リュヌションはほがすべおの蚀語構成をサポヌトし、゜ヌスコヌドはGitHubに投皿されたす 。

カットの䞋で、なぜそれが必芁なのか、どのようにしおそれが可胜になったのかを説明し、興味深い技術的な詳现にも觊れたす。

どのようにすべおが始たりたしたか


私たちは倧芏暡な䌚蚈䌚瀟Buttonで働いおいたす。 1005人のクラむアント、75人の䌚蚈士、11人の開発者がいたす。 圓瀟の䌚蚈士は、 1C䌚蚈システムに数千の顧客ベヌスの蚘録を保持しおいたす 。 デヌタベヌスを管理するには、クラりドテクノロゞヌ1cFreshを䜿甚したす。デヌタベヌスのデヌタはPostgreSQLに保存されたす。

䌚蚈士の仕事で最も難しい段階は報告です。 1Cはレポヌトを䜜成できるように芋えたすが、そのためにはデヌタベヌスの珟圚の状態が必芁です。 誰かがすべおの䞻芁な文曞をシステムに入力し、銀行取匕明现曞をむンポヌトし、必芁な䌚蚈文曞を䜜成しお実斜する必芁がありたす。 さらに、私たちの最愛の州での報告の締め切りは厳密に制限されおいるため、䌚蚈士は通垞、眠れない時間のプレッシャヌから別のプレッシャヌに生きおいたす。

䌚蚈士はどうすれば人生を楜にするこずができるのだろうず考えたした

䌚蚈ベヌスの軜埮な゚ラヌが原因で、倚くのレポヌトの問題が発生するこずが刀明したした。


リストされた問題は、1Cク゚リ蚀語を䜿甚しお簡単に芋぀けるこずができるため、クラむアントデヌタベヌスの自動監査を行うずいうアむデアが浮䞊したした。 私たちはいく぀かのリク゚ストを曞き、すべおの1Cベヌスで毎晩それらを実行し始めたした。 Googleの䟿利なプレヌトで䌚蚈士に発芋された問題を瀺し、あらゆる可胜な方法でプレヌトを空にしおおくこずを求めたした。

暙準のCOM API 1Cを介しおこれらの芁求を実行するこずはお勧めできたせん。 たず、玄1,000個のデヌタベヌスを取埗し、各デヌタベヌスですべおのク゚リを実行するには10時間かかりたす。 第二に、それは1Cサヌバヌを倧幅にロヌドしたす。これは通垞、甘くはありたせん。 監査のために、珟圚の人々の日々の仕事を遅くするこずは䞍快です。

䞀方、兞型的な1Cリク゚ストは次のようになりたす。

select doc. as Date, doc. as Number, doc.. as Inn, doc.. as CounterpartyInn, (doc..) as CounterpartyType, doc. as Description, doc. as Sum from . doc where not doc.. and doc. and doc. = (..) and (doc.) = (&Now)

SQLに非垞に䌌おいるずいう事実にもかかわらず、そのようなこずはデヌタベヌスを盎接取埗しお実行するだけでは機胜したせん。

これには、3぀の本圓の理由がありたす。

  1. デヌタベヌス内のテヌブルず列のマゞックネヌム。 これは、 1Cが芁求からの名前ぞの察応を文曞化するため、簡単に解決されたす。
  2. ネストされたプロパティ。 たずえば、SQLのdoc..はleft join 2぀のテヌブル. to doc..ず.のleft join察応しおいたす。
  3. , などの1C固有の挔算子ず関数 。 たた、適切なDBMS蚭蚈にさらに倉換する必芁がありたす。

これをすべお実珟したので、1C方蚀からのク゚リを通垞のSQLに倉換し、すべおの物理PostgreSQLサヌバヌで䞊列に実行し、結果を結合しおMS SQLの別のテヌブルに入れるナヌティリティを䜜成したした。 その結果、デヌタ収集時間は10時間から3分に短瞮されたした。

正芏衚珟


最初のバヌゞョンでは、リク゚スト倉換ロゞックを完党に正芏衚珟で実装したした。 COM API 1Cには、デヌタベヌスのGetStorage構造関数がありたす。 1Cク゚リのオブゞェクトずプロパティに察応するテヌブルずフィヌルドに関する情報を返したす。 いく぀かの正芏衚珟テンプレヌトを䜿甚しお、ある名前を別の名前に眮き換えたした。 オブゞェクトずプロパティぞのすべおの呌び出しに゚むリアスがあれば、これは非垞に簡単に実珟できたした。

すべおの面倒のほずんどは、添付プロパティによっお提䟛されたした。 1Cはそれらを関連テヌブルに栌玍するため、 from構造内のオブゞェクトの元の名前を、必芁なすべおのleft join-が存圚するサブク゚リに眮き換える必芁left join- 。

リク゚スト䟋
 select doc.. from . doc --   select doc.gen0 from (select tContractor.inn gen0 from tDoc left join tContractor on tDoc.contractorId = tContractor.id) doc


プロパティの名前を倉曎し、巊joinを生成するこずに加えお、トランスレヌタヌは倚くの倉換を䜿甚したした。 そのため、たずえば、元のク゚リのすべおのjoinは、フィヌルド (area)等䟡性に関する远加条件を提䟛する必芁がありたした。 事実、1぀のPostgreSQLデヌタベヌスには耇数の1Cクラむアントデヌタベヌスがあり、1぀のクラむアントのデヌタは、1Cがregionず呌ぶ特別な識別子によっお別のクラむアントのデヌタず異なりたす。 デヌタベヌスでは、1Cは䞀連のデフォルトむンデックスを䜜成したす。 すべおの芁求は同じクラむアント内で実行されるため、キヌの最初のコンポヌネントであるすべおに領域がありたす。 ク゚リが暙準むンデックスを䜿甚し、それらを蚘述するずきに考慮しないために、ク゚リをブロヌドキャストするずきにこの条件を自動的に远加し始めたした。

正芏衚珟を䜿甚するこずが正しい決定であるこずが刀明したした 。これにより、最終結果を迅速に取埗し、この事業党䜓から䜕か有甚なものが埗られたこずを理解できるからです。 この方法で、最も簡単に利甚できる手段で、抂念ず実隓の蚌明を行うこずをすべおの人に掚奚したす。 そしお、正芏衚珟よりもテキストを扱うずき、より簡単で効果的なものは䜕ですか

もちろん、欠点もありたす。 最初の明癜なこずは、コヌナヌの切り取りず構文の制限です。 プロパティずテヌブルの正芏衚珟はク゚リで゚むリアスを必芁ずし、䞀般に、たずえば定数文字列など、他の構成芁玠に誀っお远い぀く可胜性がありたす。

別の問題は、テキスト解析ロゞックの混乱ず、必芁なルヌルに埓ったその倉換です。 毎回、新しい機胜を実装するずき、正芏衚珟ず行のIndexOf呌び出しを組み合わせた新しい地獄のようなものを発明する必芁がありたした。これにより、元のリク゚ストの察応する芁玠が分離されたす。

そのため、たずえば、すべおのjoinにドメむンの等䟡性の条件を远加するコヌドが芋えたした。

 private string PatchJoin(string joinText, int joinPosition, string alias) { var fromPosition = queryText.LastIndexOf("from", joinPosition, StringComparison.OrdinalIgnoreCase); if (fromPosition < 0) throw new InvalidOperationException("assertion failure"); var tableMatch = tableNameRegex.Match(queryText, fromPosition); if (!tableMatch.Success) throw new InvalidOperationException("assertion failure"); var mainTableAlias = tableMatch.Groups[3].Value; var mainTableEntity = GetQueryEntity(mainTableAlias); var joinTableEntity = GetQueryEntity(alias); var condition = string.Format("{0}.{1} = {2}.{3} and ", mainTableAlias, mainTableEntity.GetAreaColumnName(), alias, joinTableEntity.GetAreaColumnName()); return joinText + condition; }

コヌドでは、 ColumnReferenceずJoinClauseをColumnReference 、元のリク゚ストのオブゞェクトモデルを凊理したかったのですが、リク゚ストテキストの正芏衚珟で芋぀かったサブストリングずオフセットのみがありたした。

このオプションは、前のオプションよりもはるかにシンプルで理解しやすいように芋えるこずに同意したす。

 private void PatchJoin(SelectClause selectClause, JoinClause joinClause) { joinClause.Condition = new AndExpression { Left = new EqualityExpression { Left = new ColumnReferenceExpression { Name = PropertyNames.area, Table = selectClause.Source }, Right = new ColumnReferenceExpression { Name = PropertyNames.area, Table = joinClause.Source } }, Right = joinClause.Condition }; }

このようなオブゞェクトモデルは、 抜象構文ツリヌ  AST ず呌ばれたす 。

AST


興味深いこずに、元のク゚リを解析したずきではなく、SQLで結果をフォヌマットするずきに、ASTが初めお衚瀺されたした。 事実は、ネストされたプロパティのサブク゚リを構築するためのロゞックは非垞に掗緎されたものであり、それを簡玠化するためにそしおSRPに埓っお、プロセス党䜓を2぀の段階に分割したした最初にサブク゚リを蚘述するオブゞェクトのツリヌを䜜成し、次にSQLで個別にシリアル化したす。 ある時点で、これがASTであるこずに気付きたした。正芏衚珟の問題を解決するには、元のリク゚ストに察しお䜜成する方法を孊ぶ必芁がありたす。

ASTずいう甚語は 、解析のニュアンスを議論するために広く䜿甚されおいたす。 このデヌタ構造は、通垞、再垰性ずルヌプがないずいう特性を備えたプログラミング蚀語に兞型的な構造をよく説明するため、 ツリヌず呌ばれたすただし、これは垞に圓おはたるわけではありたせん 。

たずえば、次のク゚リを怜蚎しおください。

 select p.surname as 'person surname' from persons p where p.name = ''

ASTの圢匏では、次のようになりたす。


図では、ノヌド-クラスのむンスタンス、矢印、および眲名-これらのクラスのプロパティ。

このようなオブゞェクトモデルは、次のようにコヌドを介しおアセンブルできたす。

 var table = new TableDeclarationClause { Name = "PersonsTable", Alias = "t" }; var selectClause = new SelectClause { FromExpression = table, WhereExpression = new EqualityExpression { Left = new ColumnReferenceExpression { Table = table, Name = "name" }, Right = new LiteralExpression { Value = "" } } }; selectClause.Fields.Add(new SelectFieldExpression { Expression = new ColumnReferenceExpression { Table = table, Name = "surname" } });

䞊蚘のASTの䟋が唯䞀の正しい䟋ではないこずに泚意しおください。 クラスの特定の構造ずクラス間の関係は、タスクの詳现によっお決たりたす。 ASTの䞻な目暙は 、問題の解決を促進し、兞型的な操䜜のパフォヌマンスを可胜な限り䟿利にするこずです。 したがっお、目的の蚀語の構造を蚘述するのがより簡単で自然であればあるほど良いです。

正芏衚珟からASTぞの移行により、倚くのハックを取り陀き、コヌドをよりわかりやすく理解しやすくするこずができたした。 同時に、今や私たちのナヌティリティは、゜ヌス蚀語のすべおの構成に぀いお知っおいお、ツリヌに適切なノヌドを䜜成する必芁がありたす。 これを行うには、ク゚リ蚀語1Cの文法ずそのためのパヌサヌを䜜成する必芁がありたした。

文法


そのため、ある時点で、元のリク゚ストのASTが必芁であるこずが明らかになりたした。 むンタヌネットにはSQLを解析しおASTを䜜成できる倚くのラむブラリがありたすが、よく芋るず、それらは有料であるか、SQLのサブセットのみをサポヌトしおいるこずがわかりたす。 さらに、SQLの1C方蚀の認識にそれらをどのように適合させるかは明確ではありたせん。

そのため、独自のパヌサヌを䜜成するこずにしたした。 パヌサヌは通垞、認識したい蚀語の文法を蚘述するこずから始めたす。 圢匏文法は、プログラミング蚀語の構造を蚘述するための叀兞的なツヌルです。 これは、掚論のルヌル、぀たり各蚀語構造の再垰的な定矩に基づいおいたす。

たずえば、これらのルヌルは算術匏の蚀語を蚘述できたす。

 E → number | (E) | E + E | E - E | E * E | E / E

このようなレコヌドは、次のように読み取るこずができたす。


出力芏則が定矩されおいるシンボルは、非終端蚘号ず呌ばれたす。 ルヌルが定矩されおおらず、蚀語の芁玠であるシンボル- タヌミナル 。 ルヌルを適甚するず、非端末から、端末のみが残るたで、他の非端末ず端末で構成される文字列を取埗できたす。 䞊蚘の䟋では、 Eは非終端蚘号であり、文字+, -, *, / 、およびnumberは、算術匏の蚀語を圢成する終端蚘号です。

特別なツヌルがありたす-パヌサヌゞェネレヌタヌは、文法の圢匏で指定された蚀語の説明に埓っお、この蚀語を認識するコヌドを生成できたす。 それらの䞭で最も有名なのは、 yacc 、 bison 、およびantlrです。 C甚の䞀般的ではないIronyラむブラリがありたす。 Habréには圌女に関する小さな蚘事が既にありたしたが、 Scott Hanselmanが圌女に぀いお投皿しおいたす。

Ironyラむブラリの䞻な機胜は、挔算子のオヌバヌロヌドを䜿甚しお、文法芏則をC#盎接蚘述できるこずです。 結果は、ルヌルを蚘述する叀兞的な圢匏に非垞に類䌌した圢匏の、非垞に玠晎らしいDSLです。

 var e = new NonTerminal("expression"); var number = new NumberLiteral("number"); e.Rule = e + "+" + e | e + "-" + e | e + "*" + e | e + "/" + e | "(" + e + ")" | number;

シンボル| は、任意のルヌルオプション論理ORを適甚できるこずを意味したす。 +蚘号は連結であり、文字は互いに続く必芁がありたす。

アむロニヌは、 解析ツリヌず抜象構文ツリヌの抂念を分離したす。 解析ツリヌは、文法芏則の䞀貫した適甚の結果であるテキスト認識プロセスの成果物です。 非終端蚘号はその内郚ノヌドに配眮され、察応するルヌルの右郚分のシンボルは子孫に分類されたす。

たずえば、ルヌルを適甚するずきの匏1+(2+3) 
e 1  E→E + E
e 2  E→E
e 3  E→番号

このような解析ツリヌに察応したす。



Parse Treeは蚀語に䟝存せず、単䞀のParseTreeNodeクラスによっおIronyで蚘述されたす。

反察に、 抜象構文ツリヌは特定のタスクによっお完党に決定され、このタスクに固有のクラスずそれらの間の関係で構成されたす。

たずえば、䞊蚘の文法のASTは、1぀のBinaryOperatorクラスのみで構成される堎合がありたす。

 public enum OperatorType { Plus, Minus, Mul, Div } public class BinaryOperator { public object Left { get; set; } public object Right { get; set; } public OperatorType Type { get; set; } }

LeftプロパティずRightプロパティはobject型です。 数倀たたは別のBinaryOperator参照できたす。


アむロニヌを䜿甚するず、文法のルヌルを適甚しながら、葉から根に向かっお順番にASTを䜜成できたす。 これを行うには、各非AstNodeCreatorデリゲヌトをAstNodeCreatorできたす。この非端末に関連付けられたルヌルのいずれかが適甚されたずきにIronyが呌び出したす。 このデリゲヌトは、送信されたParseTreeNode基づいおそれに察応するASTノヌドを䜜成し、 ParseTreeNodeリンクを戻すParseTreeNodeたす。 デリゲヌトが呌び出されるたでに、Parse Treeのすべおの子ノヌドは既に凊理されおおり、 AstNodeCreatorはすでに呌び出されおいるため、デリゲヌトの本文では、既に読み蟌たれおいる子ノヌドのAstNodeプロパティを䜿甚できたす。

このようにルヌトAstNodeに到達するず、ASTルヌトノヌドがAstNode 、この堎合はSqlQueryで圢成されたす。

䞊蚘の算術匏の文法では、AstNodeCreatorは次のようになりたす。

 var e = new NonTerminal("expression", delegate(AstContext context, ParseTreeNode node) { //  E → number, if (node.ChildNodes.Count == 1) { node.AstNode = node.ChildNodes[0].Token.Value; return; } //  E → E op E if (node.ChildNodes[0].AstNode != null && node.ChildNodes[2].AstNode != null) { node.AstNode = new BinaryOperator { Left = node.ChildNodes[0].AstNode, Operator = node.ChildNodes[1].FindTokenAndGetText(), Right = node.ChildNodes[2].AstNode }; return; } //   node.AstNode = node.ChildNodes[1].AstNode; });

そのため、Ironyの助けを借りお、最初の芁求に応じおASTを構築する方法を孊びたした。 最終的な分析では、結果のSQLク゚リASTを゜ヌスASTから取埗する必芁があるため、AST倉換甚のコヌドを効率的に構造化する方法は1぀だけです。 Visitorパタヌンはこれに圹立ちたす。

蚪問者


Visitor たたはdouble dispatch パタヌンはGoFで最も耇雑なパタヌンの1぀であり、したがっお、おそらくほずんど䜿甚されないパタヌンの1぀です。 私たちの経隓では、さたざたなASTの倉換のために、1぀のアクティブな䜿甚しか芋おいたせん。 具䜓的な䟋は、.NETのExpressionVisitorクラスです。これは、 linqプロバむダヌを実行する堎合、たたはコンパむラヌによっお生成された匏ツリヌをわずかに修正する堎合に必ず発生したす。

蚪問者はどのような問題を解決したすか
ASTで䜜業するずきによくしなければならない最も自然で必芁なこずは、ASTを文字列に倉換するこずです。 たずえば、ASTを取り䞊げたす。ロシアのテヌブル名を英語に眮き換え、 left join-を生成し、1C挔算子をデヌタベヌス挔算子に倉換した埌、PostgreSQLで実行するために送信できる文字列を出力で取埗する必芁がありたす。

この問題の可胜な解決策は次のずおりです。

 internal class SelectClause : ISqlElement { //... public void BuildSql(StringBuilder target) { target.Append("select "); for (var i = 0; i < Fields.Count; i++) { if (i != 0) target.Append(","); Fields[i].BuildSql(target); } target.Append("\r\nfrom "); From.BuildSql(target); foreach (var c in JoinClauses) { target.Append("\r\n"); c.BuildSql(target); } } }

このコヌドに぀いお、次の2぀の重芁な点を確認できたす。


次に、別のタスクを怜蚎したす。 PostgreSQLむンデックスを取埗するために、メむンテヌブルず結合されたすべおのフィヌルドのareaフィヌルドの等䟡条件を远加する必芁があるずしたす。 これを行うには、リク゚スト内のすべおのJoinClauseを確認する必芁がありたすが、可胜性のあるサブク゚リを考えるず、他のすべおのノヌドを確認する必芁がありたす。

これは、䞊蚘ず同じコヌド構造に埓う堎合、次のこずを行う必芁があるこずを意味したす。


このアプロヌチの問題は明らかです。ツリヌ䞊でさたざたな論理操䜜を行うほど、ノヌドに存圚するメ゜ッドが増え、これらのメ゜ッド間でコピヌアンドペヌストが増えたす。

蚪問者はこの問題を次の方法で解決したす 。



SQLのシリアル化の䟋は、次のように適合したす。

 internal interface ISqlElement { void Accept(SqlVisitor visitor); } internal class SqlVisitor { public virtual void Visit(ISqlElement sqlElement) { sqlElement.Accept(this); } public virtual void VisitSelectClause(SelectClause selectClause) { } //... } internal class SqlFormatter : SqlVisitor { private readonly StringBuilder target = new StringBuilder(); public override void VisitSelectClause(SelectClause selectClause) { target.Append("select "); for (var i = 0; i < selectClause.Fields.Count; i++) { if (i != 0) target.Append(","); Visit(selectClause.Fields[i]); } target.Append("\r\nfrom "); Visit(selectClause.Source); foreach (var c in selectClause.JoinClauses) { target.Append("\r\n"); Visit(c); } } } internal class SelectClause : ISqlElement { //... public void Accept(SqlVisitor visitor) { visitor.VisitSelectClause(this); } }

ダブルディスパッチずいう名前は、このスキヌムを非垞に正確に説明しおいたす。


合蚈


この蚘事では、ク゚リ蚀語1Cの翻蚳者をSQLク゚リに準備するためのレシピに぀いお詳しく説明しおいたす。 正芏衚珟を䜿った実隓を行っお、実甚的なプロトタむプを取埗し、そのものが有甚であり、先に進む䟡倀があるこずを確認したした。 そしお、恥ずかしさず苊痛なしにコヌドを芋るこずが䞍可胜になり、正芏衚珟ずゞャグリングしおも望たしい結果が埗られなかったずき、私たちは深刻な䞀歩を螏み出したした-ASTず文法に切り替えたした。 さらに、蚪問者の助けを借りお、ASTを倉換する方法を孊びたした。これにより、ある蚀語から別の蚀語ぞの翻蚳のロゞックを実珟したした。

私たちが䞀人でこのように行かず、 ドラゎンブックを開く必芁さえなかったこずは泚目に倀したす。 ASTの解析ず構築には、完成したIronyラむブラリを䜿甚したした。これにより、車茪を再発明するのではなく、適甚された問題の解決にすぐに進むこずができたした。

䌚瀟の実際の結果は、デヌタの受信速床を10時間から3分に短瞮するこずです。 これにより、アナリストは、クラむアントのビゞネスず䌚蚈士の仕事に関する仮説を迅速に実隓し、テストするこずができたした。 倚くのクラむアントがあり、それらのデヌタベヌスは5぀の物理PostgreSQLサヌバヌに分散されおいるため、これは特に䟿利です。

䞊蚘のすべおを芁玄したす。

  1. 実隓を行い、可胜な限り迅速か぀安䟡に抂念実蚌を取埗したす。
  2. 野心的な目暙を蚭定し、小さなステップでそれらに向かっお進み、埐々に機噚を目的の状態に仕䞊げたす。
  3. ほずんどのタスクには、既補の゜リュヌション、たたは少なくずも基盀が既にありたす。
  4. 解析ず文法は、通垞のビゞネスアプリケヌションに適甚できたす。
  5. 特定の問題を解決するず、䞀般的な解決策が自動的に埗られたす。

ラむブラリコヌドず䜿甚䟋がGitHubでお埅ちしおいたす 。

䜙暇には、以䞋を読むこずをお勧めしたす。

Source: https://habr.com/ru/post/J314030/

More articles:


All Articles