fork download 
  1. E=enumerate
  2. z=' '
  3. def F(b,g):
  4.  if~-b[0].isupper():yield b[0]
  5.  for a,*B in g:
  6.   if b[0]==a:yield from F(B*(B!=[z])+b[1:],g)
  7. def T(a,g):
  8.  q=[(a,b,[])for A,*b in g if A==a]
  9.  for A,b,s in q:
  10.   for i,j in E(b):
  11.    if b[i+1:]and(j==a)>b[i+1].isupper():yield b[i+1]
  12.    for J,*k in g:q+=((j==J)>(j in s))*[(J,b[:i]+k*(k!=[z])+b[i+1:],s+[j])]
  13. def f(g):
  14.  l,*g=g;D={i[0]:{}for i in g};q,R=['S'],[];l+=z,
  15.  for i,(a,*b)in E(g):
  16.   for j in(K:=[*F(b,g)]):D[a][j]=i
  17.   if' 'in K:
  18.    for j in{*T(a,g)}:D[a][j]=i
  19.  while q:
  20.   a,b=q.pop(0),l.pop(0)
  21.   if a!=b:
  22.    if~-(a in D):return
  23.    q=[t for t in g[D[a][b]][1:]if z!=t]+q;l=[b]+l;R+=D[a][b]+1,
  24.  return R
  25.  
  26. g1 = """
  27. (a+a)
  28. SF
  29. S(S+F)
  30. Fa
  31. """
  32. g2 ="""
  33. a*(a+a)
  34. STE
  35. E+TE
  36. E 
  37. TFU
  38. U*FU
  39. U 
  40. F(S)
  41. Fa
  42. """
  43.  
  44. g3 = """
  45. aaabbb
  46. SaA
  47. AaAb
  48. Ab
  49. """
  50.  
  51. g4 = """
  52. aabbb
  53. SaA
  54. AaAb
  55. Ab
  56. """
  57.  
  58. g5 = """
  59. aaabb
  60. SaA
  61. AaAb
  62. Ab
  63. """
  64.  
  65. def to_grammar(g):
  66. 	return [[*i]for i in filter(None, g.split('\n'))]
  67.  
  68.  
  69. print(f(to_grammar(g1)))
  70. print(f(to_grammar(g2)))
  71. print(f(to_grammar(g3)))
  72. print(f(to_grammar(g4)))
  73. print(f(to_grammar(g5)))
Success #stdin #stdout 0.16s 14148KB
comments (?)
stdin 
Standard input is empty
stdout 
[2, 1, 3, 3]
[1, 4, 8, 5, 7, 1, 4, 8, 6, 2, 4, 8, 6, 3, 6, 3]
[1, 2, 2, 3]
[1, 2, 3]
None
https://ideone.com/Vls9lh
language:
Python 3 (python  3.12)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!