Π§ΠΈΡ‚Π°ΠΉΡ‚Π΅ ΠΊΠ½ΠΈΠ³ΠΈ ΠΎΠ½Π»Π°ΠΉΠ½ Π½Π° Bookidrom.ru! БСсплатныС ΠΊΠ½ΠΈΠ³ΠΈ Π² ΠΎΠ΄Π½ΠΎΠΌ ΠΊΠ»ΠΈΠΊΠ΅

Π§ΠΈΡ‚Π°Ρ‚ΡŒ ΠΎΠ½Π»Π°ΠΉΠ½ Β«Π˜ΡΠΊΡƒΡΡΡ‚Π²ΠΎ программирования для UnixΒ». Π‘Ρ‚Ρ€Π°Π½ΠΈΡ†Π° 126

Автор Π Π΅ΠΉΠΌΠΎΠ½Π΄ Π­Ρ€ΠΈΠΊ Π‘Ρ‚ΠΈΠ²Π΅Π½

ΠŸΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹ уасс ΠΈ lex ΡΠ²Π»ΡΡŽΡ‚ΡΡ ΠΈΠ½ΡΡ‚Ρ€ΡƒΠΌΠ΅Π½Ρ‚Π°Π»ΡŒΠ½Ρ‹ΠΌΠΈ срСдствами для Π³Π΅Π½Π΅Ρ€Π°Ρ†ΠΈΠΈ синтаксичСских Π°Π½Π°Π»ΠΈΠ·Π°Ρ‚ΠΎΡ€ΠΎΠ² языков программирования. Π’ Π³Π»Π°Π²Π΅ 8 ΠΎΡ‚ΠΌΠ΅Ρ‡Π°Π»ΠΎΡΡŒ, Ρ‡Ρ‚ΠΎ свой ΠΏΠ΅Ρ€Π²Ρ‹ΠΉ ΠΌΠΈΠ½ΠΈ-язык программист часто создаСт случайно, Π° Π½Π΅ ΠΊΠ°ΠΊ Ρ‡Π°ΡΡ‚ΡŒ Π·Π°ΠΏΠ»Π°Π½ΠΈΡ€ΠΎΠ²Π°Π½Π½ΠΎΠΉ конструкции. Π’ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Π΅, ΠΊΠ°ΠΊ ΠΏΡ€Π°Π²ΠΈΠ»ΠΎ, появляСтся созданный Π²Ρ€ΡƒΡ‡Π½ΡƒΡŽ синтаксичСский Π°Π½Π°Π»ΠΈΠ·Π°Ρ‚ΠΎΡ€, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ ΠΏΡ€ΠΈΠ²ΠΎΠ΄ΠΈΡ‚ ΠΊ Ρ‡Ρ€Π΅Π·ΠΌΠ΅Ρ€Π½Ρ‹ΠΌ Π·Π°Ρ‚Ρ€Π°Ρ‚Π°ΠΌ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ Π½Π° сопровоТдСниС ΠΈ ΠΎΡ‚Π»Π°Π΄ΠΊΡƒ, особСнно, Ссли Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚Ρ‡ΠΈΠΊ Π½Π΅ ΠΏΠΎΠΉΠΌΠ΅Ρ‚, Ρ‡Ρ‚ΠΎ Ρ‡Π°ΡΡ‚ΡŒ Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚Π°Π½Π½ΠΎΠ³ΠΎ ΠΈΠΌ ΠΊΠΎΠ΄Π° являСтся синтаксичСским Π°Π½Π°Π»ΠΈΠ·Π°Ρ‚ΠΎΡ€ΠΎΠΌ ΠΈ Π½Π΅ ΠΎΡ‚Π΄Π΅Π»ΠΈΡ‚ Π΅Π³ΠΎ ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ ΠΎΡ‚ ΠΎΡΡ‚Π°Π»ΡŒΠ½ΠΎΠΉ части ΠΊΠΎΠ΄Π° прилоТСния. Π“Π΅Π½Π΅Ρ€Π°Ρ‚ΠΎΡ€Ρ‹ синтаксичСских Π°Π½Π°Π»ΠΈΠ·Π°Ρ‚ΠΎΡ€ΠΎΠ² ΡΠ²Π»ΡΡŽΡ‚ΡΡ инструмСнтами, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΠΏΠΎΠ·Π²ΠΎΠ»ΡΡŽΡ‚ Π΄ΠΎΠ±ΠΈΡ‚ΡŒΡΡ большСго, Ρ‡Π΅ΠΌ созданиС случайной, ΡƒΠ·ΠΊΠΎΡΠΏΠ΅Ρ†ΠΈΠ°Π»ΡŒΠ½ΠΎΠΉ Ρ€Π΅Π°Π»ΠΈΠ·Π°Ρ†ΠΈΠΈ. Они Π½Π΅ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ ΠΏΠΎΠ·Π²ΠΎΠ»ΡΡŽΡ‚ Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚Ρ‡ΠΈΠΊΡƒ Π²Ρ‹Ρ€Π°Π·ΠΈΡ‚ΡŒ ΡΠΏΠ΅Ρ†ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΡŽ Π³Ρ€Π°ΠΌΠΌΠ°Ρ‚ΠΈΠΊΠΈ Π½Π° Π±ΠΎΠ»Π΅Π΅ высоком ΡƒΡ€ΠΎΠ²Π½Π΅, Π½ΠΎ ΠΈ Ρ‡Π΅Ρ‚ΠΊΠΎ ΠΎΡ‚Π΄Π΅Π»ΡΡŽΡ‚ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ Ρ€Π΅Π°Π»ΠΈΠ·Π°Ρ†ΠΈΠΈ синтаксичСского Π°Π½Π°Π»ΠΈΠ·Π°Ρ‚ΠΎΡ€Π° ΠΎΡ‚ ΠΎΡΡ‚Π°Π»ΡŒΠ½ΠΎΠ³ΠΎ ΠΊΠΎΠ΄Π°.

Если Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚Ρ‡ΠΈΠΊ достиг Ρ‚ΠΎΠ³ΠΎ ΠΌΠΎΠΌΠ΅Π½Ρ‚Π°, ΠΊΠΎΠ³Π΄Π° планируСтся Ρ€Π΅Π°Π»ΠΈΠ·ΠΎΠ²Π°Ρ‚ΡŒ ΠΌΠΈΠ½ΠΈ-язык с нуля, Π° Π½Π΅ ΠΏΡƒΡ‚Π΅ΠΌ Ρ€Π°ΡΡˆΠΈΡ€Π΅Π½ΠΈΡ ΠΈΠ»ΠΈ внСдрСния ΡΡƒΡ‰Π΅ΡΡ‚Π²ΡƒΡŽΡ‰Π΅Π³ΠΎ языка сцСнариСв ΠΈΠ»ΠΈ Π°Π½Π°Π»ΠΈΠ·Π°Ρ‚ΠΎΡ€Π° XML, Ρ‚ΠΎ ΡƒΡ‚ΠΈΠ»ΠΈΡ‚Ρ‹ уасс ΠΈ lex, вСроятно, окаТутся Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ Π²Π°ΠΆΠ½Ρ‹ΠΌΠΈ инструмСнтами послС компилятора Π‘.

Как lex, Ρ‚Π°ΠΊ ΠΈ уасс Π³Π΅Π½Π΅Ρ€ΠΈΡ€ΡƒΡŽΡ‚ ΠΊΠΎΠ΄ для ΠΎΠ΄Π½ΠΎΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ, соотвСтствСнно, для "получСния лСксСмы ΠΈΠ· Π²Ρ…ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΠΏΠΎΡ‚ΠΎΠΊΠ°" ΠΈ для "синтаксичСского Π°Π½Π°Π»ΠΈΠ·Π° ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ лСксСм Π½Π° ΠΏΡ€Π΅Π΄ΠΌΠ΅Ρ‚ Π΅Π΅ соотвСтствия Π³Ρ€Π°ΠΌΠΌΠ°Ρ‚ΠΈΠΊΠ΅". ΠžΠ±Ρ‹Ρ‡Π½ΠΎ созданная уасс функция синтаксичСского Π°Π½Π°Π»ΠΈΠ·Π°Ρ‚ΠΎΡ€Π° Π²Ρ‹Π·Ρ‹Π²Π°Π΅Ρ‚ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΡŽ Π°Π½Π°Π»ΠΈΠ·Π°Ρ‚ΠΎΡ€Π° лСксСм, сгСнСрированного lex, ΠΊΠ°ΠΆΠ΄Ρ‹ΠΉ Ρ€Π°Π· ΠΏΡ€ΠΈ нСобходимости получСния ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅ΠΉ лСксСмы. Если Π² Π³/асс-сгСнСрированном синтаксичСском Π°Π½Π°Π»ΠΈΠ·Π°Ρ‚ΠΎΡ€Π΅ Π²ΠΎΠΎΠ±Ρ‰Π΅ Π½Π΅ сущСствуСт написанных ΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚Π΅Π»Π΅ΠΌ ΠΎΠ±Ρ€Π°Ρ‚Π½Ρ‹Ρ… Π²Ρ‹Π·ΠΎΠ²ΠΎΠ² Π‘, Ρ‚ΠΎ Ρ€Π°Π±ΠΎΡ‚Π° Π΄Π°Π½Π½ΠΎΠ³ΠΎ Π°Π½Π°Π»ΠΈΠ·Π°Ρ‚ΠΎΡ€Π° сводится Ρ‚ΠΎΠ»ΡŒΠΊΠΎ ΠΊ ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΊΠ΅ синтаксиса. Π’ΠΎΠ·Π²Ρ€Π°Ρ‰Π°Π΅ΠΌΠΎΠ΅ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ сообщит Π²Ρ‹Π·Ρ‹Π²Π°ΡŽΡ‰Π΅ΠΉ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ΅ ΠΎ совпадСнии Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ… с ΠΎΠΆΠΈΠ΄Π°Π΅ΠΌΠΎΠΉ Π³Ρ€Π°ΠΌΠΌΠ°Ρ‚ΠΈΠΊΠΎΠΉ.

Π’ Π±ΠΎΠ»Π΅Π΅ распространСнном Π²Π°Ρ€ΠΈΠ°Π½Ρ‚Π΅ ΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΡΠΊΠΈΠΉ Π‘-ΠΊΠΎΠ΄, встроСнный Π² сгСнСрированный синтаксичСский Π°Π½Π°Π»ΠΈΠ·Π°Ρ‚ΠΎΡ€, заполняСт Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ динамичСскиС структуры Π΄Π°Π½Π½Ρ‹Ρ… ΠΊΠ°ΠΊ ΠΏΠΎΠ±ΠΎΡ‡Π½Ρ‹ΠΉ эффСкт синтаксичСского Π°Π½Π°Π»ΠΈΠ·Π° Π²Π²ΠΎΠ΄Π°. Если ΠΌΠΈΠ½ΠΈ-язык являСтся Π΄Π΅ΠΊΠ»Π°Ρ€Π°Ρ‚ΠΈΠ²Π½Ρ‹ΠΌ, Ρ‚ΠΎ ΠΏΡ€ΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅ ΠΌΠΎΠΆΠ΅Ρ‚ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ эти структуры Π΄Π°Π½Π½Ρ‹Ρ… нСпосрСдствСнно. Π’ случаС ΠΈΠΌΠΏΠ΅Ρ€Π°Ρ‚ΠΈΠ²Π½ΠΎΠ³ΠΎ ΠΌΠΈΠ½ΠΈ-языка структуры Π΄Π°Π½Π½Ρ‹Ρ… ΠΌΠΎΠ³ΡƒΡ‚ Π²ΠΊΠ»ΡŽΡ‡Π°Ρ‚ΡŒ Π² сСбя Π΄Π΅Ρ€Π΅Π²ΠΎ грамматичСского Ρ€Π°Π·Π±ΠΎΡ€Π°, ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ΅ Π½Π΅ΠΌΠ΅Π΄Π»Π΅Π½Π½ΠΎ пСрСдаСтся Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ ΠΎΡ†Π΅Π½ΠΎΡ‡Π½ΠΎΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ.

Π£Ρ‚ΠΈΠ»ΠΈΡ‚Π° уасс ΠΈΠΌΠ΅Π΅Ρ‚ довольно нСкрасивый интСрфСйс β€” Ρ‡Π΅Ρ€Π΅Π· экспортируСмыС Π³Π»ΠΎΠ±Π°Π»ΡŒΠ½Ρ‹Π΅ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Π΅ с ΠΈΠΌΠ΅Π½Π½Ρ‹ΠΌ прСфиксом ΡƒΡƒ_. Π­Ρ‚ΠΎ связано с Ρ‚Π΅ΠΌ, Ρ‡Ρ‚ΠΎ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ° уасс ΠΏΡ€Π΅Π΄ΡˆΠ΅ΡΡ‚Π²ΠΎΠ²Π°Π»Π° структурам Π‘. ЀактичСски уасс ΠΏΡ€Π΅Π΄ΡˆΠ΅ΡΡ‚Π²ΠΎΠ²Π°Π»Π° самому языку Π‘; пСрвая рСализация ΡƒΡ‚ΠΈΠ»ΠΈΡ‚Ρ‹ Π±Ρ‹Π»Π° написана Π½Π° языкС Π’, ΠΏΡ€Π΅Π΄ΡˆΠ΅ΡΡ‚Π²Π΅Π½Π½ΠΈΠΊΠ΅ Π‘. Π“Ρ€ΡƒΠ±Ρ‹ΠΉ, хотя ΠΈ эффСктивный Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ, ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌΡ‹ΠΉ Π² сгСнСрированных уасс синтаксичСских Π°Π½Π°Π»ΠΈΠ·Π°Ρ‚ΠΎΡ€Π°Ρ… ΠΏΡ€ΠΈ ΠΏΠΎΠΏΡ‹Ρ‚ΠΊΠ°Ρ… восстановлСния послС ошибок Π°Π½Π°Π»ΠΈΠ·Π° (лСксСмы Π²Ρ‹Ρ‚Π°Π»ΠΊΠΈΠ²Π°ΡŽΡ‚ΡΡ Π΄ΠΎ Ρ‚Π΅Ρ… ΠΏΠΎΡ€, ΠΏΠΎΠΊΠ° Π½Π΅ обнаруТится явная ошибка), Ρ‚Π°ΠΊΠΆΠ΅ ΠΌΠΎΠΆΠ΅Ρ‚ привСсти ΠΊ ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌΠ°ΠΌ, Π²ΠΊΠ»ΡŽΡ‡Π°Ρ ΡƒΡ‚Π΅Ρ‡ΠΊΠΈ памяти.

Если Π²Ρ‹ создаСтС Π΄Π΅Ρ€Π΅Π²ΡŒΡ грамматичСского Ρ€Π°Π·Π±ΠΎΡ€Π° с использованиСм Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ malloc ΠΈ Π½Π°Ρ‡ΠΈΠ½Π°Π΅Ρ‚Π΅ Π²Ρ‹Ρ‚Π°Π»ΠΊΠΈΠ²Π°Ρ‚ΡŒ элСмСнты стСка Π² процСссС восстановлСния послС ошибки, Ρ‚ΠΎ Π²Π°ΠΌ Π½Π΅ удастся Π²ΠΎΡΡΡ‚Π°Π½ΠΎΠ²ΠΈΡ‚ΡŒ (Π²Ρ‹ΡΠ²ΠΎΠ±ΠΎΠ΄ΠΈΡ‚ΡŒ) ΠΏΠ°ΠΌΡΡ‚ΡŒ. Как ΠΏΡ€Π°Π²ΠΈΠ»ΠΎ, ΡƒΡ‚ΠΈΠ»ΠΈΡ‚Π° уасс Π½Π΅ способна это Π΄Π΅Π»Π°Ρ‚ΡŒ, ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ Π½Π΅ ΠΈΠΌΠ΅Π΅Ρ‚ достаточных свСдСний ΠΎ содСрТимом стСка. Если Π±Ρ‹ Π³/дсс-Π°Π½Π°Π»ΠΈΠ·Π°Ρ‚ΠΎΡ€ Π±Ρ‹Π» написан Π½Π° Π‘++, Ρ‚ΠΎ ΠΎΠ½ ΠΌΠΎΠ³ Π±Ρ‹ "ΠΏΡ€Π΅Π΄ΠΏΠΎΠ»ΠΎΠΆΠΈΡ‚ΡŒ", Ρ‡Ρ‚ΠΎ значСния ΡΠ²Π»ΡΡŽΡ‚ΡΡ классами, ΠΈ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ дСструктор. Π’ "Ρ€Π΅Π°Π»ΡŒΠ½Ρ‹Ρ…" компиляторах ΡƒΠ·Π»Ρ‹ Π΄Π΅Ρ€Π΅Π²Π° грамматичСского Ρ€Π°Π·Π±ΠΎΡ€Π° Π³Π΅Π½Π΅Ρ€ΠΈΡ€ΡƒΡŽΡ‚ΡΡ с ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ распрСдСлитСля динамичСской памяти, поэтому ΡƒΠ·Π»Ρ‹ "Π½Π΅ Π²Ρ‹Ρ‚Π΅ΠΊΠ°ΡŽΡ‚", Π½ΠΎ Ρ‚Π°ΠΊ ΠΈΠ»ΠΈ ΠΈΠ½Π°Ρ‡Π΅, проявляСтся логичСская ΡƒΡ‚Π΅Ρ‡ΠΊΠ° памяти, ΠΊΠΎΡ‚ΠΎΡ€ΡƒΡŽ Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ ΠΏΡ€ΠΎΠ°Π½Π°Π»ΠΈΠ·ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΡΠΎΠ·Π΄Π°Ρ‚ΡŒ систСму восстановлСния послС ошибок ΠΏΡ€ΠΎΠΌΡ‹ΡˆΠ»Π΅Π½Π½ΠΎΠ³ΠΎ уровня.

Π‘Ρ‚ΠΈΠ² ДТонсон.

ΠŸΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ° lex β€” Π³Π΅Π½Π΅Ρ€Π°Ρ‚ΠΎΡ€ лСксичСских Π°Π½Π°Π»ΠΈΠ·Π°Ρ‚ΠΎΡ€ΠΎΠ². Она Π²Ρ…ΠΎΠ΄ΠΈΡ‚ Π² состав Ρ‚ΠΎΠ³ΠΎ ΠΆΠ΅ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½ΠΎΠ³ΠΎ сСмСйства, Ρ‡Ρ‚ΠΎ ΠΈ grep(1) ΠΈ awk( 1), Π½ΠΎ являСтся Π±ΠΎΠ»Π΅Π΅ ΠΌΠΎΡ‰Π½ΠΎΠΉ, ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ позволяСт ΠΏΠΎΠ΄Π³ΠΎΡ‚ΠΎΠ²ΠΈΡ‚ΡŒ ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ»ΡŒΠ½Ρ‹ΠΉ Π‘-ΠΊΠΎΠ΄ для выполнСния ΠΏΡ€ΠΈ ΠΊΠ°ΠΆΠ΄ΠΎΠΌ совпадСнии. ΠŸΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ° ΠΏΡ€ΠΈΠ½ΠΈΠΌΠ°Π΅Ρ‚ Π΄Π΅ΠΊΠ»Π°Ρ€Π°Ρ‚ΠΈΠ²Π½Ρ‹ΠΉ ΠΌΠΈΠ½ΠΈ-язык ΠΈ создаСт "скСлСтный" Π‘-ΠΊΠΎΠ΄.

Для Ρ‚ΠΎΠ³ΠΎ Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΏΠΎΠ½ΡΡ‚ΡŒ Ρ€Π°Π±ΠΎΡ‚Ρƒ /Π΅Ρ…-сгСнСрированного Π°Π½Π°Π»ΠΈΠ·Π°Ρ‚ΠΎΡ€Π° лСксСм, сущСствуСт Π³Ρ€ΡƒΠ±Ρ‹ΠΉ, Π½ΠΎ ΡƒΠ΄ΠΎΠ±Π½Ρ‹ΠΉ способ β€” мыслСнная инвСрсия Ρ€Π°Π±ΠΎΡ‚Ρ‹ grep(1). Π’ΠΎΠ³Π΄Π° ΠΊΠ°ΠΊ grep(1) ΠΏΡ€ΠΈΠ½ΠΈΠΌΠ°Π΅Ρ‚ ΠΎΠ΄Π½ΠΎ рСгулярноС Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠ΅ ΠΈ Π²ΠΎΠ·Π²Ρ€Π°Ρ‰Π°Π΅Ρ‚ список совпадСний Π²ΠΎ Π²Ρ…ΠΎΠ΄Π½ΠΎΠΌ ΠΏΠΎΡ‚ΠΎΠΊΠ΅ Π΄Π°Π½Π½Ρ‹Ρ…, ΠΊΠ°ΠΆΠ΄Ρ‹ΠΉ Π²Ρ‹Π·ΠΎΠ² /Π΅Π»Π³-сгСнСрированного Π°Π½Π°Π»ΠΈΠ·Π°Ρ‚ΠΎΡ€Π° лСксСм ΠΏΡ€ΠΈΠ½ΠΈΠΌΠ°Π΅Ρ‚ список рСгулярных Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠΉ ΠΈ ΡƒΠΊΠ°Π·Ρ‹Π²Π°Π΅Ρ‚, ΠΊΠ°ΠΊΠΎΠ΅ Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠ΅ встрСчаСтся ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠΌ Π² ΠΏΠΎΡ‚ΠΎΠΊΠ΅ Π΄Π°Π½Π½Ρ‹Ρ….

Π Π°Π·Π΄Π΅Π»Π΅Π½ΠΈΠ΅ Π°Π½Π°Π»ΠΈΠ·Π° Π²Π²ΠΎΠ΄Π° Π½Π° распознаваниС лСксСм ΠΈ синтаксичСский Π°Π½Π°Π»ΠΈΠ· ΠΏΠΎΡ‚ΠΎΠΊΠ° лСксСм являСтся ΠΏΠΎΠ»Π΅Π·Π½Ρ‹ΠΌ тактичСским ΠΏΡ€ΠΈΠ΅ΠΌΠΎΠΌ, Π΄Π°ΠΆΠ΅ Ссли Π² Ρ…ΠΎΠ΄Π΅ Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚ΠΊΠΈ ΡƒΡ‚ΠΈΠ»ΠΈΡ‚Ρ‹ Yacc ΠΈ Lex Π½Π΅ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ΡΡ, Π° "лСксСмы" Π½Π΅ ΠΈΠΌΠ΅ΡŽΡ‚ Π½ΠΈΡ‡Π΅Π³ΠΎ ΠΎΠ±Ρ‰Π΅Π³ΠΎ с ΠΎΠ±Ρ‹Ρ‡Π½Ρ‹ΠΌΠΈ лСксСмами Π² компиляторС. НСоднократно я убСТдался, Ρ‡Ρ‚ΠΎ Ρ€Π°Π·Π΄Π΅Π»Π΅Π½ΠΈΠ΅ ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠΈ Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ… Π½Π° Π΄Π²Π° уровня Π·Π½Π°Ρ‡ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ ΡƒΠΏΡ€ΠΎΡ‰Π°Π΅Ρ‚ ΠΊΠΎΠ΄ ΠΈ ΠΎΠ±Π»Π΅Π³Ρ‡Π°Π΅Ρ‚ ΠΏΠΎΠ½ΠΈΠΌΠ°Π½ΠΈΠ΅, нСсмотря Π½Π° ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ, Π²Π½Π΅ΡΠ΅Π½Π½ΡƒΡŽ самим Ρ€Π°Π·Π΄Π΅Π»Π΅Π½ΠΈΠ΅ΠΌ.

Π“Π΅Π½Ρ€ΠΈ БпСнсСр.

Π£Ρ‚ΠΈΠ»ΠΈΡ‚Π° lex Π±Ρ‹Π»Π° написана для Π°Π²Ρ‚ΠΎΠΌΠ°Ρ‚ΠΈΠ·Π°Ρ†ΠΈΠΈ создания лСксичСских Π°Π½Π°Π»ΠΈΠ·Π°Ρ‚ΠΎΡ€ΠΎΠ² (Π°Π½Π°Π»ΠΈΠ·Π°Ρ‚ΠΎΡ€ΠΎΠ² лСксСм) для компиляторов. ВпослСдствии оказалось, Ρ‡Ρ‚ΠΎ ΠΎΠ½Π° ΠΈΠΌΠ΅Π΅Ρ‚ ΡƒΠ΄ΠΈΠ²ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ ΡˆΠΈΡ€ΠΎΠΊΠΈΠΉ Π΄ΠΈΠ°ΠΏΠ°Π·ΠΎΠ½ примСнСния для Π΄Ρ€ΡƒΠ³ΠΈΡ… Π²ΠΈΠ΄ΠΎΠ² распознавания ΠΎΠ±Ρ€Π°Π·Ρ†ΠΎΠ², ΠΈ с Ρ‚Π΅Ρ… ΠΏΠΎΡ€ описываСтся ΠΊΠ°ΠΊ "ΡˆΠ²Π΅ΠΉΡ†Π°Ρ€ΡΠΊΠΈΠΉ Π½ΠΎΠΆ Unix-программирования"94.

ΠŸΡ€ΠΈ Ρ€Π°Π·Ρ€Π΅ΡˆΠ΅Π½ΠΈΠΈ любой ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌΡ‹ распознавания ΠΎΠ±Ρ€Π°Π·Ρ†ΠΎΠ² ΠΈΠ»ΠΈ создания ΠΊΠΎΠ½Π΅Ρ‡Π½ΠΎΠ³ΠΎ Π°Π²Ρ‚ΠΎΠΌΠ°Ρ‚Π°, Π² ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΌ всС Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Ρ‹Π΅ Π²Ρ…ΠΎΠ΄Π½Ρ‹Π΅ сигналы ΡƒΠΌΠ΅Ρ‰Π°ΡŽΡ‚ΡΡ Π² Π±Π°ΠΉΡ‚Π΅, ΡƒΡ‚ΠΈΠ»ΠΈΡ‚Π° lex позволяСт ΡΠ³Π΅Π½Π΅Ρ€ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ ΠΊΠΎΠ΄, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ Π±ΡƒΠ΄Π΅Ρ‚ Π±ΠΎΠ»Π΅Π΅ эффСктивным ΠΈ Π½Π°Π΄Π΅ΠΆΠ½Ρ‹ΠΌ, Ρ‡Π΅ΠΌ созданный Π²Ρ€ΡƒΡ‡Π½ΡƒΡŽ ΠΊΠΎΠ½Π΅Ρ‡Π½Ρ‹ΠΉ Π°Π²Ρ‚ΠΎΠΌΠ°Ρ‚.

Π”ΠΆΠΎΠ½ ДТарвис (John Jarvis) Π² Π₯ΠΎΠ»ΠΌΠ΄Π΅Π»Π΅ (Holmdel β€” лаборатория AT&T) использовал lex для поиска нСисправностСй Π² ΠΌΠΎΠ½Ρ‚Π°ΠΆΠ½Ρ‹Ρ… ΠΏΠ»Π°Ρ‚Π°Ρ…. Он сканировал ΠΏΠ»Π°Ρ‚Ρƒ, примСнял ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΈΠΊΡƒ кодирования Ρ†Π΅ΠΏΠ΅ΠΉ для прСдставлСния Π³Ρ€Π°Π½ΠΈΡ† областСй Π½Π° ΠΏΠ»Π°Ρ‚Π΅, Π° Π·Π°Ρ‚Π΅ΠΌ использовал Lex для опрСдСлСния ΠΎΠ±Ρ€Π°Π·Ρ†ΠΎΠ², с ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… ΠΌΠΎΠΆΠ½ΠΎ Π±Ρ‹Π»ΠΎ Π±Ρ‹ Π½Π°Ρ…ΠΎΠ΄ΠΈΡ‚ΡŒ распространСнныС ошибки ΠΌΠΎΠ½Ρ‚Π°ΠΆΠ°.

Майк Π›Π΅Π΅ΠΊ.

Π’Π°ΠΆΠ½Π΅Π΅ Ρ‚ΠΎ, Ρ‡Ρ‚ΠΎ ΠΌΠΈΠ½ΠΈ-язкк /Π΅Π΄Π³-спСцификации являСтся Π±ΠΎΠ»Π΅Π΅ высокоуровнСвым ΠΈ ΠΊΠΎΠΌΠΏΠ°ΠΊΡ‚Π½Ρ‹ΠΌ, Ρ‡Π΅ΠΌ эквивалСнтный Π‘-ΠΊΠΎΠ΄, написанный Π²Ρ€ΡƒΡ‡Π½ΡƒΡŽ. Доступны ΠΌΠΎΠ΄ΡƒΠ»ΠΈ для использования flex (вСрсия с ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚Ρ‹ΠΌ исходным ΠΊΠΎΠ΄ΠΎΠΌ) с Perl (ΠΈΡ… ΠΌΠΎΠΆΠ½ΠΎ Π½Π°ΠΉΡ‚ΠΈ Π² Web с ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ Ρ„Ρ€Π°Π·Ρ‹ "lex perl"), Π° Ρ‚Π°ΠΊΠΆΠ΅ ΠΈΠ΄Π΅Π½Ρ‚ΠΈΡ‡Π½ΠΎ Ρ€Π°Π±ΠΎΡ‚Π°ΡŽΡ‰Π°Ρ рСализация, которая являСтся Ρ‡Π°ΡΡ‚ΡŒΡŽ срСдства PLY Π² Python.

lex Π³Π΅Π½Π΅Ρ€ΠΈΡ€ΡƒΠ΅Ρ‚ синтаксичСскиС Π°Π½Π°Π»ΠΈΠ·Π°Ρ‚ΠΎΡ€Ρ‹, Ρ€Π°Π±ΠΎΡ‚Π°ΡŽΡ‰ΠΈΠ΅ Π½Π° порядок ΠΌΠ΅Π΄Π»Π΅Π½Π½Π΅Π΅ написанных Π²Ρ€ΡƒΡ‡Π½ΡƒΡŽ. Однако Π΄Π°Π½Π½Ρ‹ΠΉ Ρ„Π°ΠΊΡ‚ Π½Π΅ являСтся ΠΏΡ€ΠΈΡ‡ΠΈΠ½ΠΎΠΉ для Ρ€ΡƒΡ‡Π½ΠΎΠ³ΠΎ кодирования, это Π°Ρ€Π³ΡƒΠΌΠ΅Π½Ρ‚ Π² ΠΏΠΎΠ»ΡŒΠ·Ρƒ создания с ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ lex ΠΏΡ€ΠΎΡ‚ΠΎΡ‚ΠΈΠΏΠ° ΠΈ Π΄ΠΎΡ€Π°Π±ΠΎΡ‚ΠΊΠΈ ΠΊΠΎΠ΄Π° Π²Ρ€ΡƒΡ‡Π½ΡƒΡŽ, Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Ссли ΠΏΡ€ΠΎΡ‚ΠΎΡ‚ΠΈΠΏ ΠΏΠΎΠΊΠ°Π·Ρ‹Π²Π°Π΅Ρ‚ Ρ€Π΅Π°Π»ΡŒΠ½ΠΎΠ΅ "Π±ΡƒΡ‚Ρ‹Π»ΠΎΡ‡Π½ΠΎΠ΅ Π³ΠΎΡ€Π»Ρ‹ΡˆΠΊΠΎ".

Π£Ρ‚ΠΈΠ»ΠΈΡ‚Π° уасс β€” Π³Π΅Π½Π΅Ρ€Π°Ρ‚ΠΎΡ€ синтаксичСских Π°Π½Π°Π»ΠΈΠ·Π°Ρ‚ΠΎΡ€ΠΎΠ². Она Ρ‚Π°ΠΊΠΆΠ΅ Π±Ρ‹Π»Π° написана для Π°Π²Ρ‚ΠΎΠΌΠ°Ρ‚ΠΈΠ·Π°Ρ†ΠΈΠΈ части Ρ€Π°Π±ΠΎΡ‚Ρ‹ ΠΏΠΎ написанию компиляторов, уасс ΠΏΡ€ΠΈΠ½ΠΈΠΌΠ°Π΅Ρ‚ Π½Π° Π²Ρ…ΠΎΠ΄Π΅ Π³Ρ€Π°ΠΌΠΌΠ°Ρ‚ΠΈΡ‡Π΅ΡΠΊΡƒΡŽ ΡΠΏΠ΅Ρ†ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΡŽ Π² Π΄Π΅ΠΊΠ»Π°Ρ€Π°Ρ‚ΠΈΠ²Π½ΠΎΠΌ ΠΌΠΈΠ½ΠΈ-языкС, ΠΏΠΎΠ΄ΠΎΠ±Π½ΠΎΠΌ BNF (Backus-Naur Form β€” запись Бэкуса-Наура), с Π‘-ΠΊΠΎΠ΄ΠΎΠΌ, связанным с ΠΊΠ°ΠΆΠ΄Ρ‹ΠΌ элСмСнтом Π³Ρ€Π°ΠΌΠΌΠ°Ρ‚ΠΈΠΊΠΈ. Данная ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ° Π³Π΅Π½Π΅Ρ€ΠΈΡ€ΡƒΠ΅Ρ‚ ΠΊΠΎΠ΄ для Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ синтаксичСского Π°Π½Π°Π»ΠΈΠ·Π°, которая ΠΏΡ€ΠΈ Π²Ρ‹Π·ΠΎΠ²Π΅ ΠΏΡ€ΠΈΠ½ΠΈΠΌΠ°Π΅Ρ‚ тСкст, ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΠΉ Π³Ρ€Π°ΠΌΠΌΠ°Ρ‚ΠΈΠΊΠ΅ ΠΈΠ· Π²Ρ…ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΠΏΠΎΡ‚ΠΎΠΊΠ°. По ΠΌΠ΅Ρ€Π΅ распознавания ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ грамматичСского элСмСнта, функция Π°Π½Π°Π»ΠΈΠ·Π°Ρ‚ΠΎΡ€Π° запускаСт связанный Π‘-ΠΊΠΎΠ΄.

ΠšΠΎΠΌΠ±ΠΈΠ½Π°Ρ†ΠΈΡ ΡƒΡ‚ΠΈΠ»ΠΈΡ‚ lex ΠΈ уасс вСсьма эффСктивна для написания языковых ΠΈΠ½Ρ‚Π΅Ρ€ΠΏΡ€Π΅Ρ‚Π°Ρ‚ΠΎΡ€ΠΎΠ² всСх Π²ΠΈΠ΄ΠΎΠ². Π₯отя Π±ΠΎΠ»ΡŒΡˆΠΈΠ½ΡΡ‚Π²Ρƒ Unix-программистов Π½ΠΈΠΊΠΎΠ³Π΄Π° Π½Π΅ придСтся Π²Ρ‹ΠΏΠΎΠ»Π½ΡΡ‚ΡŒ Π΄Π°Π½Π½Ρ‹ΠΉ Π²ΠΈΠ΄ ΡƒΠ½ΠΈΠ²Π΅Ρ€ΡΠ°Π»ΡŒΠ½ΠΎΠ³ΠΎ построСния компилятора, для ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ³ΠΎ Π·Π°Π΄ΡƒΠΌΡ‹Π²Π°Π»ΠΈΡΡŒ эти инструмСнты, ΠΎΠ½ΠΈ Ρ‡Ρ€Π΅Π·Π²Ρ‹Ρ‡Π°ΠΉΠ½ΠΎ ΠΏΠΎΠ»Π΅Π·Π½Ρ‹ для написания Π°Π½Π°Π»ΠΈΠ·Π°Ρ‚ΠΎΡ€ΠΎΠ² синтаксиса ΠΊΠΎΠ½Ρ„ΠΈΠ³ΡƒΡ€Π°Ρ†ΠΈΠΎΠ½Π½Ρ‹Ρ… Ρ„Π°ΠΉΠ»ΠΎΠ² ΠΈ ΡƒΠ·ΠΊΠΎΡΠΏΠ΅Ρ†ΠΈΠ°Π»ΡŒΠ½Ρ‹Ρ… ΠΌΠΈΠ½ΠΈ-языков.