lexer.go 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717
  1. /*
  2. * Public Domain Software
  3. *
  4. * I (Matthias Ladkau) am the author of the source code in this file.
  5. * I have placed the source code in this file in the public domain.
  6. *
  7. * For further information see: http://creativecommons.org/publicdomain/zero/1.0/
  8. */
  9. package parser
  10. import (
  11. "bytes"
  12. "encoding/json"
  13. "fmt"
  14. "regexp"
  15. "strconv"
  16. "strings"
  17. "unicode"
  18. "unicode/utf8"
  19. )
  20. var namePattern = regexp.MustCompile("^[A-Za-z][A-Za-z0-9]*$")
  21. var numberPattern = regexp.MustCompile("^[0-9].*$")
  22. /*
  23. LexToken represents a token which is returned by the lexer.
  24. */
  25. type LexToken struct {
  26. ID LexTokenID // Token kind
  27. Pos int // Starting position (in bytes)
  28. Val string // Token value
  29. Identifier bool // Flag if the value is an identifier (not quoted and not a number)
  30. Lline int // Line in the input this token appears
  31. Lpos int // Position in the input line this token appears
  32. }
  33. /*
  34. Equal checks if this LexToken equals another LexToken. Returns also a message describing
  35. what is the found difference.
  36. */
  37. func (n LexToken) Equals(other LexToken, ignorePosition bool) (bool, string) {
  38. var res = true
  39. var msg = ""
  40. if n.ID != other.ID {
  41. res = false
  42. msg += fmt.Sprintf("ID is different %v vs %v\n", n.ID, other.ID)
  43. }
  44. if !ignorePosition && n.Pos != other.Pos {
  45. res = false
  46. msg += fmt.Sprintf("Pos is different %v vs %v\n", n.Pos, other.Pos)
  47. }
  48. if n.Val != other.Val {
  49. res = false
  50. msg += fmt.Sprintf("Val is different %v vs %v\n", n.Val, other.Val)
  51. }
  52. if n.Identifier != other.Identifier {
  53. res = false
  54. msg += fmt.Sprintf("Identifier is different %v vs %v\n", n.Identifier, other.Identifier)
  55. }
  56. if !ignorePosition && n.Lline != other.Lline {
  57. res = false
  58. msg += fmt.Sprintf("Lline is different %v vs %v\n", n.Lline, other.Lline)
  59. }
  60. if !ignorePosition && n.Lpos != other.Lpos {
  61. res = false
  62. msg += fmt.Sprintf("Lpos is different %v vs %v\n", n.Lpos, other.Lpos)
  63. }
  64. if msg != "" {
  65. var buf bytes.Buffer
  66. out, _ := json.MarshalIndent(n, "", " ")
  67. buf.WriteString(string(out))
  68. buf.WriteString("\nvs\n")
  69. out, _ = json.MarshalIndent(other, "", " ")
  70. buf.WriteString(string(out))
  71. msg = fmt.Sprintf("%v%v", msg, buf.String())
  72. }
  73. return res, msg
  74. }
  75. /*
  76. PosString returns the position of this token in the origianl input as a string.
  77. */
  78. func (t LexToken) PosString() string {
  79. return fmt.Sprintf("Line %v, Pos %v", t.Lline, t.Lpos)
  80. }
  81. /*
  82. String returns a string representation of a token.
  83. */
  84. func (t LexToken) String() string {
  85. prefix := ""
  86. if !t.Identifier {
  87. prefix = "v:" // Value is not an identifier
  88. }
  89. switch {
  90. case t.ID == TokenEOF:
  91. return "EOF"
  92. case t.ID == TokenError:
  93. return fmt.Sprintf("Error: %s (%s)", t.Val, t.PosString())
  94. case t.ID == TokenCOMMENT:
  95. return fmt.Sprintf("c:'%s'", t.Val)
  96. case t.ID > TOKENodeSYMBOLS && t.ID < TOKENodeKEYWORDS:
  97. return fmt.Sprintf("%s", strings.ToUpper(t.Val))
  98. case t.ID > TOKENodeKEYWORDS:
  99. return fmt.Sprintf("<%s>", strings.ToUpper(t.Val))
  100. case len(t.Val) > 20:
  101. // Special case for very long values
  102. return fmt.Sprintf("%s%.10q...", prefix, t.Val)
  103. }
  104. return fmt.Sprintf("%s%q", prefix, t.Val)
  105. }
  106. /*
  107. KeywordMap is a map of keywords - these require spaces between them
  108. */
  109. var KeywordMap = map[string]LexTokenID{
  110. // Sink definition
  111. "sink": TokenSINK,
  112. "kindmatch": TokenKINDMATCH,
  113. "scopematch": TokenSCOPEMATCH,
  114. "statematch": TokenSTATEMATCH,
  115. "priority": TokenPRIORITY,
  116. "suppresses": TokenSUPPRESSES,
  117. // Function definition
  118. "func": TokenFUNC,
  119. // Boolean operators
  120. "and": TokenAND,
  121. "or": TokenOR,
  122. "not": TokenNOT,
  123. // String operators
  124. "like": TokenLIKE,
  125. "hasprefix": TokenHASPREFIX,
  126. "hassuffix": TokenHASSUFFIX,
  127. // List operators
  128. "in": TokenIN,
  129. "notin": TokenNOTIN,
  130. // Constant terminals
  131. "false": TokenFALSE,
  132. "true": TokenTRUE,
  133. "null": TokenNULL,
  134. // Conditional statements
  135. "if": TokenIF,
  136. "elif": TokenELIF,
  137. "else": TokenELSE,
  138. // Loop statements
  139. "for": TokenFOR,
  140. "break": TokenBREAK,
  141. "continue": TokenCONTINUE,
  142. }
  143. /*
  144. SymbolMap is a map of special symbols which will always be unique - these will separate unquoted strings
  145. Symbols can be maximal 2 characters long.
  146. */
  147. var SymbolMap = map[string]LexTokenID{
  148. // Condition operators
  149. ">=": TokenGEQ,
  150. "<=": TokenLEQ,
  151. "!=": TokenNEQ,
  152. "==": TokenEQ,
  153. ">": TokenGT,
  154. "<": TokenLT,
  155. // Grouping symbols
  156. "(": TokenLPAREN,
  157. ")": TokenRPAREN,
  158. "[": TokenLBRACK,
  159. "]": TokenRBRACK,
  160. "{": TokenLBRACE,
  161. "}": TokenRBRACE,
  162. // Sequence symbols
  163. ".": TokenDOT,
  164. ",": TokenCOMMA,
  165. ":": TokenCOLON,
  166. ";": TokenSEMICOLON,
  167. // Arithmetic operators
  168. "+": TokenPLUS,
  169. "-": TokenMINUS,
  170. "*": TokenTIMES,
  171. "/": TokenDIV,
  172. "//": TokenDIVINT,
  173. "%": TokenMODINT,
  174. // Assignment statement
  175. ":=": TokenASSIGN,
  176. }
  177. // Lexer
  178. // =====
  179. /*
  180. RuneEOF is a special rune which represents the end of the input
  181. */
  182. const RuneEOF = -1
  183. /*
  184. Function which represents the current state of the lexer and returns the next state
  185. */
  186. type lexFunc func(*lexer) lexFunc
  187. /*
  188. Lexer data structure
  189. */
  190. type lexer struct {
  191. name string // Name to identify the input
  192. input string // Input string of the lexer
  193. pos int // Current rune pointer
  194. line int // Current line pointer
  195. lastnl int // Last newline position
  196. width int // Width of last rune
  197. start int // Start position of the current red token
  198. tokens chan LexToken // Channel for lexer output
  199. }
  200. /*
  201. Lex lexes a given input. Returns a channel which contains tokens.
  202. */
  203. func Lex(name string, input string) chan LexToken {
  204. l := &lexer{name, input, 0, 0, 0, 0, 0, make(chan LexToken)}
  205. go l.run()
  206. return l.tokens
  207. }
  208. /*
  209. LexToList lexes a given input. Returns a list of tokens.
  210. */
  211. func LexToList(name string, input string) []LexToken {
  212. var tokens []LexToken
  213. for t := range Lex(name, input) {
  214. tokens = append(tokens, t)
  215. }
  216. return tokens
  217. }
  218. /*
  219. Main loop of the lexer.
  220. */
  221. func (l *lexer) run() {
  222. if skipWhiteSpace(l) {
  223. for state := lexToken; state != nil; {
  224. state = state(l)
  225. if !skipWhiteSpace(l) {
  226. break
  227. }
  228. }
  229. }
  230. close(l.tokens)
  231. }
  232. /*
  233. next returns the next rune in the input and advances the current rune pointer
  234. if peek is 0. If peek is >0 then the nth character is returned without advancing
  235. the rune pointer.
  236. */
  237. func (l *lexer) next(peek int) rune {
  238. // Check if we reached the end
  239. if int(l.pos) >= len(l.input) {
  240. return RuneEOF
  241. }
  242. // Decode the next rune
  243. pos := l.pos
  244. if peek > 0 {
  245. pos += peek - 1
  246. }
  247. r, w := utf8.DecodeRuneInString(l.input[pos:])
  248. if peek == 0 {
  249. l.width = w
  250. l.pos += l.width
  251. }
  252. return r
  253. }
  254. /*
  255. backup sets the pointer one rune back. Can only be called once per next call.
  256. */
  257. func (l *lexer) backup(width int) {
  258. if width == 0 {
  259. width = l.width
  260. }
  261. l.pos -= width
  262. }
  263. /*
  264. startNew starts a new token.
  265. */
  266. func (l *lexer) startNew() {
  267. l.start = l.pos
  268. }
  269. /*
  270. emitToken passes a token back to the client.
  271. */
  272. func (l *lexer) emitToken(t LexTokenID) {
  273. if t == TokenEOF {
  274. l.emitTokenAndValue(t, "", false)
  275. return
  276. }
  277. if l.tokens != nil {
  278. l.tokens <- LexToken{t, l.start, l.input[l.start:l.pos], false,
  279. l.line + 1, l.start - l.lastnl + 1}
  280. }
  281. }
  282. /*
  283. emitTokenAndValue passes a token with a given value back to the client.
  284. */
  285. func (l *lexer) emitTokenAndValue(t LexTokenID, val string, identifier bool) {
  286. if l.tokens != nil {
  287. l.tokens <- LexToken{t, l.start, val, identifier, l.line + 1, l.start - l.lastnl + 1}
  288. }
  289. }
  290. /*
  291. emitError passes an error token back to the client.
  292. */
  293. func (l *lexer) emitError(msg string) {
  294. if l.tokens != nil {
  295. l.tokens <- LexToken{TokenError, l.start, msg, false, l.line + 1, l.start - l.lastnl + 1}
  296. }
  297. }
  298. // Helper functions
  299. // ================
  300. /*
  301. skipWhiteSpace skips any number of whitespace characters. Returns false if the parser
  302. reaches EOF while skipping whitespaces.
  303. */
  304. func skipWhiteSpace(l *lexer) bool {
  305. r := l.next(0)
  306. for unicode.IsSpace(r) || unicode.IsControl(r) || r == RuneEOF {
  307. if r == '\n' {
  308. l.line++
  309. l.lastnl = l.pos
  310. }
  311. r = l.next(0)
  312. if r == RuneEOF {
  313. l.emitToken(TokenEOF)
  314. return false
  315. }
  316. }
  317. l.backup(0)
  318. return true
  319. }
  320. /*
  321. lexTextBlock lexes a block of text without whitespaces. Interprets
  322. optionally all one or two letter tokens.
  323. */
  324. func lexTextBlock(l *lexer, interpretToken bool) {
  325. r := l.next(0)
  326. if interpretToken {
  327. // Check if we start with a known symbol
  328. nr := l.next(1)
  329. if _, ok := SymbolMap[strings.ToLower(string(r)+string(nr))]; ok {
  330. l.next(0)
  331. return
  332. }
  333. if _, ok := SymbolMap[strings.ToLower(string(r))]; ok {
  334. return
  335. }
  336. }
  337. for !unicode.IsSpace(r) && !unicode.IsControl(r) && r != RuneEOF {
  338. if interpretToken {
  339. // Check if we find a token in the block
  340. if _, ok := SymbolMap[strings.ToLower(string(r))]; ok {
  341. l.backup(0)
  342. return
  343. }
  344. nr := l.next(1)
  345. if _, ok := SymbolMap[strings.ToLower(string(r)+string(nr))]; ok {
  346. l.backup(0)
  347. return
  348. }
  349. }
  350. r = l.next(0)
  351. }
  352. if r != RuneEOF {
  353. l.backup(0)
  354. }
  355. }
  356. /*
  357. lexNumberBlock lexes a block potentially containing a number.
  358. */
  359. func lexNumberBlock(l *lexer) {
  360. r := l.next(0)
  361. for !unicode.IsSpace(r) && !unicode.IsControl(r) && r != RuneEOF {
  362. if !unicode.IsNumber(r) && r != '.' {
  363. if r == 'e' {
  364. l1 := l.next(1)
  365. l2 := l.next(2)
  366. if l1 != '+' || !unicode.IsNumber(l2) {
  367. break
  368. }
  369. l.next(0)
  370. l.next(0)
  371. } else {
  372. break
  373. }
  374. }
  375. r = l.next(0)
  376. }
  377. if r != RuneEOF {
  378. l.backup(0)
  379. }
  380. }
  381. // State functions
  382. // ===============
  383. /*
  384. lexToken is the main entry function for the lexer.
  385. */
  386. func lexToken(l *lexer) lexFunc {
  387. // Check if we got a quoted value or a comment
  388. n1 := l.next(1)
  389. n2 := l.next(2)
  390. // Parse comments
  391. if (n1 == '/' && n2 == '*') || n1 == '#' {
  392. return lexComment
  393. }
  394. // Parse strings
  395. if (n1 == '"' || n1 == '\'') || (n1 == 'r' && (n2 == '"' || n2 == '\'')) {
  396. return lexValue
  397. }
  398. // Lex a block of text and emit any found tokens
  399. l.startNew()
  400. // First try to parse a number
  401. lexNumberBlock(l)
  402. keywordCandidate := strings.ToLower(l.input[l.start:l.pos])
  403. // Check for number
  404. if numberPattern.MatchString(keywordCandidate) {
  405. _, err := strconv.ParseFloat(keywordCandidate, 64)
  406. if err == nil {
  407. l.emitTokenAndValue(TokenNUMBER, keywordCandidate, false)
  408. return lexToken
  409. }
  410. }
  411. if len(keywordCandidate) > 0 {
  412. l.backup(l.pos - l.start)
  413. }
  414. lexTextBlock(l, true)
  415. keywordCandidate = strings.ToLower(l.input[l.start:l.pos])
  416. // Check for keyword
  417. token, ok := KeywordMap[keywordCandidate]
  418. if !ok {
  419. // Check for symbol
  420. token, ok = SymbolMap[keywordCandidate]
  421. }
  422. if ok {
  423. // A known token was found
  424. l.emitToken(token)
  425. } else {
  426. if !namePattern.MatchString(keywordCandidate) {
  427. l.emitError(fmt.Sprintf("Cannot parse identifier '%v'. Identifies may only contain [a-zA-Z] and [a-zA-Z0-9] from the second character", keywordCandidate))
  428. return nil
  429. }
  430. // An identifier was found
  431. l.emitTokenAndValue(TokenIDENTIFIER, keywordCandidate, true)
  432. }
  433. return lexToken
  434. }
  435. /*
  436. lexValue lexes a string value.
  437. Values can be declared in different ways:
  438. ' ... ' or " ... "
  439. Characters are parsed between quotes (escape sequences are interpreted)
  440. r' ... ' or r" ... "
  441. Characters are parsed plain between quote
  442. */
  443. func lexValue(l *lexer) lexFunc {
  444. var endToken rune
  445. l.startNew()
  446. allowEscapes := false
  447. r := l.next(0)
  448. // Check if we have a raw quoted string
  449. if q := l.next(1); r == 'r' && (q == '"' || q == '\'') {
  450. endToken = q
  451. l.next(0)
  452. } else {
  453. allowEscapes = true
  454. endToken = r
  455. }
  456. r = l.next(0)
  457. rprev := ' '
  458. lLine := l.line
  459. lLastnl := l.lastnl
  460. for (!allowEscapes && r != endToken) ||
  461. (allowEscapes && (r != endToken || rprev == '\\')) {
  462. if r == '\n' {
  463. lLine++
  464. lLastnl = l.pos
  465. }
  466. rprev = r
  467. r = l.next(0)
  468. if r == RuneEOF {
  469. l.emitError("Unexpected end while reading string value (unclosed quotes)")
  470. return nil
  471. }
  472. }
  473. if allowEscapes {
  474. val := l.input[l.start+1 : l.pos-1]
  475. // Interpret escape sequences right away
  476. if endToken == '\'' {
  477. // Escape double quotes in a single quoted string
  478. val = strings.Replace(val, "\"", "\\\"", -1)
  479. }
  480. s, err := strconv.Unquote("\"" + val + "\"")
  481. if err != nil {
  482. l.emitError(err.Error() + " while parsing string")
  483. return nil
  484. }
  485. l.emitTokenAndValue(TokenSTRING, s, true)
  486. } else {
  487. l.emitTokenAndValue(TokenSTRING, l.input[l.start+2:l.pos-1], true)
  488. }
  489. // Set newline
  490. l.line = lLine
  491. l.lastnl = lLastnl
  492. return lexToken
  493. }
  494. /*
  495. lexComment lexes comments.
  496. */
  497. func lexComment(l *lexer) lexFunc {
  498. // Consume initial /*
  499. r := l.next(0)
  500. if r == '#' {
  501. l.startNew()
  502. for r != '\n' && r != RuneEOF {
  503. r = l.next(0)
  504. }
  505. l.emitTokenAndValue(TokenCOMMENT, l.input[l.start:l.pos-1], false)
  506. if r == RuneEOF {
  507. return nil
  508. }
  509. l.line++
  510. } else {
  511. l.next(0)
  512. lLine := l.line
  513. lLastnl := l.lastnl
  514. l.startNew()
  515. r = l.next(0)
  516. for r != '*' && l.next(1) != '/' {
  517. if r == '\n' {
  518. lLine++
  519. lLastnl = l.pos
  520. }
  521. r = l.next(0)
  522. if r == RuneEOF {
  523. l.emitError("Unexpected end while reading comment")
  524. return nil
  525. }
  526. }
  527. l.emitTokenAndValue(TokenCOMMENT, l.input[l.start:l.pos-1], false)
  528. // Consume final /
  529. l.next(0)
  530. // Set newline
  531. l.line = lLine
  532. l.lastnl = lLastnl
  533. }
  534. return lexToken
  535. }