pyformlang 0.1.14

pyformlang

用于操作形式语法的python库。一般来说，它可以用来更好地理解算法的形式化方式。

安装

pip3 install pyformlang

来源

大多数算法来自自动机理论、语言和计算的介绍 （第2版）作者：John E.Hopcroft、Rajeev Motwani和Jeferey D.Ullman。

索引文法来自alfred v.aho的原始论文index文法-上下文无关文法的扩展。

hopcroft最小化算法的实现：Implementation of Hopcroft's Algorithm, Hang Zhou

Intersection CFG/Regex

用法

正则表达式

pyformlang包含一个基本的regex读取器。可用的运算符是：

• 连接，默认运算符，可以用 空格或点（.）
• 联合体，用或+
表示
• 克莱恩星，由*

也可以使用括号。与空格、、、+、*、（、）和$不同的符号可以是字母表的一部分，连续字符被视为单个符号。epsilon符号可以是epsilon或$。

frompyformlang.regular_expressionimportRegexregex=Regex("(a-|a a b)*")

有限自动机

pyformlang包含几个有限自动机，所有这些自动机在它们可以描述的语言中都是等价的。一般来说，状态必须由一个pyformlang.finite嫒u automaton.state对象表示，而符号必须由一个pyformlang.finite嫒u automaton.symbol对象表示。当类不模棱两可时，也可以使用原始值。此外，epsilon转换是类的元素：pyformlang.finite_automaton.epsilon。

确定性自动机

它们代表确定性自动机，即每个阶段只有一个可能的下一个状态，没有epsilon跃迁。

frompyformlang.finite_automatonimportDeterministicFiniteAutomatonfrompyformlang.finite_automatonimportStatefrompyformlang.finite_automatonimportSymbol# Declaration of the DFAdfa=DeterministicFiniteAutomaton()# Creation of the statesstate0=State(0)state1=State(1)state2=State(2)state3=State(3)# Creation of the symbolssymb_a=Symbol("a")symb_b=Symbol("b")symb_c=Symbol("c")symb_d=Symbol("d")# Add a start statedfa.add_start_state(state0)# Add two final statesdfa.add_final_state(state2)dfa.add_final_state(state3)# Create transitionsdfa.add_transition(state0,symb_a,state1)dfa.add_transition(state1,symb_b,state1)dfa.add_transition(state1,symb_c,state2)dfa.add_transition(state1,symb_d,state3)# Check if a word is accepteddfa.accepts([symb_a,symb_b,symb_c])

非确定性自动机

非确定性自动机的一种表示法，即在每个阶段可能有几个下一个状态但没有epsilon跃迁的自动机。

frompyformlang.finite_automatonimportNondeterministicFiniteAutomatonfrompyformlang.finite_automatonimportStatefrompyformlang.finite_automatonimportSymbol# Definition of the NFAnfa=NondeterministicFiniteAutomaton()# Declare the statesstate0=State(0)state1=State(1)state2=State(2)state3=State(3)state4=State(4)# Declare the symbolssymb_a=Symbol("a")symb_b=Symbol("b")symb_c=Symbol("c")symb_d=Symbol("d")# Add a start statenfa.add_start_state(state0)# Add a final statenfa.add_final_state(state4)nfa.add_final_state(state3)# Add the transitionsnfa.add_transition(state0,symb_a,state1)nfa.add_transition(state1,symb_b,state1)nfa.add_transition(state1,symb_c,state2)nfa.add_transition(state1,symb_d,state3)nfa.add_transition(state1,symb_c,state4)nfa.add_transition(state1,symb_b,state4)# Check if a word is acceptednfa.accepts([symb_a,symb_b,symb_c])# Check if a NFA is deterministicnfa.is_deterministic()# False# Get the equivalent deterministic automatondfa=nfa.to_deterministic()

epsilon非确定性自动机

它表示允许epsilon转换的非确定性自动机。

frompyformlang.finite_automatonimportEpsilonNFA,State,Symbol,Epsilon# Declaration of the symbols and the statesepsilon=Epsilon()plus=Symbol("+")minus=Symbol("-")point=Symbol(".")digits=[Symbol(x)forxinrange(10)]states=[State("q"+str(x))forxinrange(6)]# Creattion of the Epsilon NFAenfa=EpsilonNFA()enfa.add_start_state(states[0])enfa.add_final_state(states[5])enfa.add_transition(states[0],epsilon,states[1])enfa.add_transition(states[0],plus,states[1])enfa.add_transition(states[0],minus,states[1])fordigitindigits:enfa.add_transition(states[1],digit,states[1])enfa.add_transition(states[1],digit,states[4])enfa.add_transition(states[2],digit,states[3])enfa.add_transition(states[3],digit,states[3])enfa.add_transition(states[1],point,states[2])enfa.add_transition(states[4],point,states[3])enfa.add_transition(states[3],epsilon,states[5])# Checks if a word is acceptedenfa.accepts([plus,digits[1],point,digits[9]])

正则表达式和有限自动机

由于regex和有限自动机是等价的，所以可以将一个转化为另一个。

frompyformlang.finite_automatonimportEpsilonNFA,State,Symbol,Epsilonenfa=EpsilonNFA()state0=State(0)state1=State(1)symb_a=Symbol("0")symb_b=Symbol("1")enfa.add_start_state(state0)enfa.add_final_state(state1)enfa.add_transition(state0,symb_a,state0)enfa.add_transition(state1,symb_b,state0)enfa.add_transition(state1,symb_b,state1)# Turn a finite automaton into a regex...regex=enfa.to_regex()# And turn it back into an epsilon non deterministic automatonenfa2=regex.to_epsilon_nfa()

上下文无关语法

我们在这里表示上下文无关文法。像有限自动机一样，需要使用类pyformlang.cfg.variable和pyformlang.cfg.terminal来表示变量和终端。产品需要表示为pyformlang.cfg.production。此外，epsilon终端是pyformlang.cfg.epsilon的成员。

frompyformlang.cfgimportProduction,Variable,Terminal,CFG,Epsilon# Creation of variablesvar_useless=Variable("USELESS")var_S=Variable("S")var_B=Variable("B")# Creation of terminalster_a=Terminal("a")ter_b=Terminal("b")ter_c=Terminal("c")# Creation of productionsp0=Production(var_S,[ter_a,var_S,var_B])p1=Production(var_useless,[ter_a,var_S,var_B])p2=Production(var_S,[var_useless])p4=Production(var_B,[ter_b])p5=Production(var_useless,[])# Creation of the CFGcfg=CFG({var_useless,var_S},{ter_a,ter_b},var_S,{p0,p1,p2,p4,p5})# Check for containmentcfg.contains([Epsilon()])cfg.contains([ter_a,ter_b])

下推自动机

对于下推自动机，有以下对象：pyformlang.pda.state表示状态，pyformlang.pda.symbol表示符号，pyformlang.pda.stacksymbol表示堆栈符号。

pda可以按最终状态接受，也可以按空堆栈接受。提供了将一种类型转换为另一种类型的函数。

frompyformlang.pdaimportPDA,State,StackSymbol,Symbol,Epsilon# Declare statesq=State("#STARTTOFINAL#")q0=State("q0")# Declare symbolse=Symbol("e")i=Symbol("i")# Declare stack symbolsZ=StackSymbol("Z")Z0=StackSymbol("Z0")# Create the PDApda=PDA(states={q,q0},input_symbols={i,e},stack_alphabet={Z,Z0},start_state=q,start_stack_symbol=Z0,final_states={q0})# Add transitionspda.add_transition(q,i,Z,q,(Z,Z))pda.add_transition(q,i,Z0,q,(Z,Z0))pda.add_transition(q,e,Z,q,[])pda.add_transition(q,Epsilon(),Z0,q0,[])# Transformation to a PDA accepting by empty stackpda_empty_stack=pda.to_empty_stack()# Transformation to a PDA accepting by final statepda_final_state=pda_empty_stack.to_final_state()

cfg和pda

由于cfg和pda是等价的，一个可以将一个转换成另一个，但是需要注意pda是否接受空堆栈和final状态。cfg和pda之间的转换是在pda被空堆栈接受时完成的

frompyformlang.cfgimportProduction,Variable,Terminal,CFGter_a=Terminal("a")ter_b=Terminal("b")ter_c=Terminal("c")var_S=Variable("S")productions={Production(var_S,[ter_a,var_S,ter_b]),Production(var_S,[ter_c])}cfg=CFG(productions=productions,start_symbol=var_S)# Convert into a PDA accepting by final statepda_empty_stack=cfg.to_pda()# Go to final statepda_final_state=pda_empty_stack.to_final_state()# Go back to empty stack, necessary to transform into a CFGpda_empty_stack=pda_final_state.to_empty_stack()# Transform the PDA into a CFGcfg=pda_empty_stack.to_cfg()

索引文法

索引文法是具有可复制堆栈的文法。在索引语法中，规则可以采用4种形式（sigma是堆栈）：

• endrule：这只是将变量转换为一个终端，例如a[sigma]->；a
• productionrule：我们把一些东西推到堆栈上，例如a[sigma]->；b[f sigma]
• consumptionrule：我们从堆栈中消费一些东西，例如西格玛]->；C[西格玛]
• copicationrule：我们复制堆栈，例如a[sigma]->；b[sigma]c[sigma]

frompyformlang.indexed_grammarimportRulesfrompyformlang.indexed_grammarimportConsumptionRulefrompyformlang.indexed_grammarimportEndRulefrompyformlang.indexed_grammarimportProductionRulefrompyformlang.indexed_grammarimportDuplicationRulefrompyformlang.indexed_grammarimportIndexedGrammarl_rules=[]# Initialization rulesl_rules.append(ProductionRule("S","Cinit","end"))l_rules.append(ProductionRule("Cinit","C","b"))l_rules.append(ConsumptionRule("end","C","T"))l_rules.append(EndRule("T","epsilon"))# C[cm sigma] -> cm C[sigma]l_rules.append(ConsumptionRule("cm","C","B0"))l_rules.append(DuplicationRule("B0","A0","C"))l_rules.append(EndRule("A0","cm"))rules=Rules(l_rules)i_grammar=IndexedGrammar(rules)self.assertTrue(i_grammar.is_empty())

标签：

• 框架
• add
• 形式
• state
• transition
• states
• 文法
• pda

欢迎加入QQ群-->： 979659372

推荐PyPI第三方库

• chaudio

  程序化音乐合成

• odoo8-addon-sale-reason-to-export

  在销售订单中导出的原因

• intake-elasticsearch

  ElasticSearch插件

• opal-referral

  蛋白石参考门户插件

• oidc-validators

  验证OIDC令牌

• dwl

  下载youtube“稍后观看”视频的愚蠢命令。

• seamicro-ml2

  OpenStack网络

• input_reader

  使用受argparse启发的api定义和读取输入文件

• odoo8-addon-product-dimension

  产品尺寸

• notifycenter

  通知中心python sdk

• CLIP-Crawler

  一个包装器/爬虫程序，用于从校园生活集成平台（clip.fct.unl.pt）获取信息

• bashcolor

  在bash终端中获取颜色的简单库

• PigLatinTranslation

  小猪拉丁语翻译微服务

• csu-radartools

  用于极化雷达检索的python工具。

• parse-landsat-xml

  搜索大量陆地卫星元数据文件，然后下载生成的陆地卫星场景。